101. 对称二叉树

[swiftwind0405]

方法一：递归（分而治之）

解题思想：

• 转化为：左右子树是否是镜像
• 分解为：树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像

代码：

var isSymmetric = function(root) {
    if (!root) return true;

    const isMirror = (l, r) => {
        if (!l && !r) return true;
        if (l && r && (l.val === r.val) &&
            isMirror(l.left, r.right) && 
            isMirror(l.right, r.left)
        ) {
            return true;
        }
        return false;
    } 

    return isMirror(root.left, root.right);
};

复杂度分析：

• 时间复杂度：O(n)，访问所有的节点；
• 空间复杂度：O(n)，递归的堆栈，堆栈的深度为二叉树的高度，在最差情况下，就是节点的个数。

方法二：迭代