共计 1924 个字符,预计需要花费 5 分钟才能阅读完成。
本专题旨在分享刷 Leecode 过程发现的一些思路乏味或者有价值的题目。【当然是基于 js 进行解答】。
递归算法始终是 leetcode 中等难度习题的重点类型之一,所以关键性显而易见。
题目相干
- 原题地址: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
-
题目形容:
请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
然而上面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
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
值相等: -
其次是思考 边界条件
- 如果初始是一颗 空的树,那间接返回后果,也算对称;
- 同步比对时,在任意一步,只有呈现不满足 L 的左节点 = R 的右节点 且 L 的右节点,= R 的左节点,则提前结束,返回 false;
- 如果可能比对到两边同时完结,那么阐明是 对称树,返回 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);
}
有没有发现,递归类题目最初都是 代码写进去后不长,然而了解比拟吃力,所以更须要本人尝试着去抓逻辑重点。
很倡议大家在看完之后,本人手写一次代码跑跑看
很倡议大家在看完之后,本人手写一次代码跑跑看
很倡议大家在看完之后,本人手写一次代码跑跑看
因为很多边界条件的写法和细节,其实才是调试过程中最常常出 bug 的。
另外,大家能够利用本题的思路,去 试着解一下 这道递归回溯的题目 – 树的子结构 从而坚固所学 https://leetcode-cn.com/probl…
那么,简简单单一道题又搞定了!
正文完