101. 对称二叉树

1. 题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [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

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

2. 解题思路

（1）递归：
递归的思路比较简单，具体实现思路如下：

• 首先判断当前树是否为空，空则直接返回true，否则就左子树的左子树和右子树的右子树是否相等
• 如果左节点或者右节点为空时，就比较对应的右节点或左节点是否为空，为空则返回true，否则就返回false
• 如果左右节点都不为空，就判断左节点的左节点和右节点的右节点是否相等
• 如果相等，就传入该节点的子节点进行递归，否则就返回false

递归的时间复杂度为O(n)，空间复杂度为O(n)。

（2）迭代：
迭代方法需要借助队列来实现。

迭代的时间复杂度为O(n)，空间复杂度为O(n)。

3. 代码实现

递归：

/**
 * 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 isSameTree(root.left, root.right)
};
const isSameTree = (l, r) => {
    if(!l) return r === null
    if(!r) return l === null
    if(l.val !== r.val) return false
    return isSameTree(l.left, r.right,) && isSameTree(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}
 */
const isSymmetric = (root) => {
  if (!root) return true
  let queue = [root.left, root.right]
  while (queue.length > 0) {
    let t1 = queue.shift(), t2 = queue.shift()
    if (t1 === null && t2 === null) continue
    if (t1 === null || t2 === null || t1.val !== t2.val) return false
    queue.push(t1.left, t2.right, t1.right, t2.left)
  }
  return true
}

4. 提交结果

递归：

迭代：