101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

递归

var isSymmetric = function(root) {
    if(!root) return true
    var isEqual = function(left, right) {
        if(!left && !right) return true
        if(!left || !right) return false
        return left.val === right.val
         && isEqual(left.left, right.right)
         && isEqual(left.right, right.left)
    }
    return isEqual(root.left, root.right)
};
// O(n) 空间：O(n)

迭代

利用栈来记录比较的过程，实际上，递归就使用了调用栈，所以这里我们可以使用栈来模拟递归的过程

• 首先根的左右子树入栈
• 将左右子树出栈，比较两个数是否互为镜像
• 如果左右子树的根节点值相等，则将左子树的 left 、右子树的 right 、左子树的 right 、右子树的 left 依次入栈
• 继续出栈（一次出栈两个进行比较）……. 依次循环出栈入栈，直到栈为空

var isSymmetric = function(root) {
    if(!root) return true
    let stack = [root.left, root.right]
    while(stack.length) {
        let right = stack.pop()
        let left = stack.pop()
        if(left && right) {
            if(left.val !== right.val) return false
            stack.push(left.left)
            stack.push(right.right)
            stack.push(left.right)
            stack.push(right.left)
        } else if(left || right) {
            return false
        }
    }
    return true
};