101. 对称二叉树

[Geekhyt]

原题链接

递归

先明确，所谓“对称”，也就是两个树的根节点相同且

• 第一个树的左子树与第二个树的右子树镜像对称。
• 第一个树的右子树与第二个树的左子树镜像对称。

const isSymmetric = function(root) {
    if (root === null) return true
    return isEqual(root.left, root.right) // 比较左右子树是否对称
};

const isEqual = function(left, right) {
    // 递归终止条件
    if (left === null && right === null) return true // 对称
    if (left === null || right === null) return false // 不对称
    // 比较左右子树的 root 值以及左右子树是否对称
    return left.val === right.val
        && isEqual(left.left, right.right)
        && isEqual(left.right, right.left)
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)

[lyvvq9296]

这种递归的空间复杂度要怎么判断呢？

[GTRgoSky]

// 迭代
var isSymmetric = function(root) {
    const stack = [root.left, root.right];
    while(stack.length) {
        let curL = stack.shift();
        let curR = stack.shift();
        if (curL === curR) {
            continue;
        }
        if (!curL || !curR) {
            return false;
        }
        if (curL.val !== curR.val) {
            return false;
        }
        stack.push(curL.left, curR.right);
        stack.push(curL.right, curR.left);
    }
    return true;
};

// 递归
var isSymmetric = function(root) {
    function compare(L, R) {
        if (L === R) return true;
        if (!L || !R) return false;
        if (L.val != R.val) return false;
        return compare(L.left, R.right) && compare(L.right, R.left);
    }
    return compare(root.left, root.right);
};