小程序管理平台_网站优化网络推广seo_网站推广优化网址_搜狗seo排名软件

leetcode 101

思路

对称二叉树也就是比较根节点的左右子树的值，根节点左子树的值要等于右子树的值，左子树的左子树值要等于右子树的右子树的值，具体比较是用根节点 root 的左右子树来比较
这里考虑使用递归法或者是层序遍历来实现
层序遍历就是每一层把要比较的两个值先放入，我们来模拟一下实现
首先初始化设置queue = [2,2]
然后出栈left = 2, right = 2
出栈以后要判断以下这些情况：

1. 左子树 = null 右子树 !== null 不对称
2. 左子树 !== null 右子树 = null 不对称
3. 右子树 = null 左子树 = null 对称
4. 左子树.val != 右子树.val 不对称
5. 左子树val = 右子树val，那么继续进行遍历
   下面要比较的是左子树的左孩子和右子树的右孩子(外侧和外侧比较)
   queue.push(left.left, right.right)
   然后还要比较左子树的右孩子和右子树的左孩子(内侧和内侧)
   queue.push(left.right, right.left)
   此时queue = [3,3,4,4]
   然后出栈：left = 3 right = 3相等，继续入队 queue = [4,4,5,5]
   queue = [4,4,5,5,6,6]
   然后继续循环上诉操作可得到结果

图片来自代码随想录

方法1-后序遍历

var isSymmetric = function (root) {const deep = (left, right) => {// 左存在，右不存在if (left && !right) return false// 左不存在，右存在if (!left && right) return false;// 左右都不存在if (!left && !right) return true;// 左右都存在，但值不相等if (left.val !== right.val) return false;// 左右都存在，且值相等const outside = deep(left.left, right.right)const inside = deep(left.right, right.left)return outside && inside;}return deep(root.left, root.right)
};

方法2-层序遍历

// 前序遍历中左右
var preorderTraversal = function (root) {const queue = [root.left, root.right];while (queue.length) {const left = queue.shift();const right = queue.shift();// 左存在，右不存在if (left && !right) return false;// 左不存在，右存在if (!left && right) return false;// 左右节点都不存在if (!left && !right) continue;// 左右节点值不相等if (left.val !== right.val) {return false;}// 左右节点值相等queue.push(left.left, right.right)queue.push(left.right, right.left)}return true
}