leetcode101-对称二叉树

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
}