Leetcode|Leetcode 题解系列 -- 对称二叉树（递归） Leetcode题解系列--对称二叉树（

本专题旨在分享刷Leecode过程发现的一些思路有趣或者有价值的题目。【当然是基于js进行解答】。
递归算法一直是leetcode 中等难度习题的重点类型之一，所以关键性不言而喻。
题目相关

原题地址: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
题目描述：

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1 / \ 22 / \ / \ 34 43

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1 / \ 22 \\ 33

Tips 考虑某些同学可能比较少用js来刷leetcode，我们在这里简单介绍下,关于树类型的数据输入,在js里的表示。形如上题中的内容，给定二叉树的输入，其实并非一个数组，而应该是如下所示: 每个节点是一个object:

const root = { val: 3, left: { // left表示当前节点的左侧子节点 val: 9, left: null, // 对照上图可以看到节点9没有左右子节点 right: null, }, right: { val: 20, left: { val: 15, // 对照上图可以看到节点15没有左右子节点 left: null, right: null, }, right: { val: 7, // 对照上图可以看到节点7没有左右子节点 left: null, right: null, }, } }

思路解析首先这道题是明显的递归类题目，而递归类的题目一般就是以下几个步骤：

提取递归部分的逻辑
判断边界条件

文章图片

首先整体的逻辑上，要判定一棵树是镜像二叉树的话，肯定是要从根节点的左右节点开始进行对比，在遍历过程遇到的每一组节点（用L和R表示），都要满足L的左节点 = R的右节点且 L的右节点 = R的左节点由于会递归比较，所以这里相等其实就只要是val值相等:

文章图片
其次是考虑边界条件
1. 如果初始是一颗空的树，那直接返回结果，也算对称；
2. 同步比对时，在任意一步，只要出现不满足L的左节点 = R的右节点且 L的右节点，= R的左节点，则提前结束，返回false；
3. 如果能够比对到两边同时结束，那么说明是对称树，返回true；

那么按照前文说的，先写出递归部分的逻辑：

var recuCompare = function (L, R) { if(!L && !R) { // 说明同时比对同时结束或者是两边均无该子节点 return true; } if(!L || !R || L.val !== R.val ) { // 扣除第一种情况那么!L 或者！R说明左右不同时结束，也就是出现不对称 return false; } return recuCompare(L.left, R.right) && recuCompare(L.right, R.left); // 继续往下比对 }

那么补上递归起始条件部分，完整代码就可以得出了。
完整代码

/** * Definition for a binary tree node. * function TreeNode(val) { *this.val = val; *this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {boolean} */ var isSymmetric = function(root) { if(!root) {return true}; return recuCompare(root.left, root.right) }; var recuCompare = function (L, R) { if(!L && !R) { return true; } if(!L || !R || L.val !== R.val ){ return false; } return recuCompare(L.left, R.right) && recuCompare(L.right, R.left); }

有没有发现，递归类题目最后都是代码写出来后不长，但是理解比较吃力，所以更需要自己尝试着去抓逻辑重点。
【Leetcode|Leetcode 题解系列 -- 对称二叉树（递归）】很建议大家在看完之后，自己手写一次代码跑跑看
很建议大家在看完之后，自己手写一次代码跑跑看
很建议大家在看完之后，自己手写一次代码跑跑看
因为很多边界条件的写法和细节，其实才是调试过程中最经常出bug的。
另外，大家可以利用本题的思路，去试着解一下这道递归回溯的题目--树的子结构从而巩固所学 https://leetcode-cn.com/probl...
那么，简简单单一道题又搞定了！