06对称二叉树

题目

101. 对称二叉树思路

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：


输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：


输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内

100 <= Node.val <= 100

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

思路

正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）

左节点为空，右节点不为空，不对称，return false

左不为空，右为空，不对称 return false

左右都为空，对称，返回true

此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：

左右都不为空，比较节点数值，不相同就return false

TS实现

递归法


const compare = (left: TreeNode, right: TreeNode) => {
    // 判断为null的情况
    if(left === null && right === null) {
        return true;
    } else if (left === null && right !== null) {
        return false;
    } else if (left !== null && right === null) {
        return false;
    } else if (left.val !== right.val) {
        return false;
    } 
    
    const outSide = compare(left.left, right.right);
    const inSide = compare(left.right, right.left);
    const isSame = outSide && inSide;
    return isSame;
}


function isSymmetric(root: TreeNode | null): boolean {
    if (!root) return true;
    return compare(root.left, root.right);
};

迭代法

使用队列


function isSymmetric(root: TreeNode | null): boolean {
    if (!root) return true;

    const queue: TreeNode[] = [];
		// 这里需要入栈left和right，两个两个拿出来对比
    queue.push(root.left);
    queue.push(root.right);

    while (queue.length) {
        const left = queue.shift();
        const right = queue.shift();

        if (!left && !right) {
            continue;
        }
        else if (!left || !right || left.val !== right.val) return false;

				// 这里的顺序就是内侧外侧对比的顺序
        queue.push(left.left);
        queue.push(right.right);
        queue.push(left.right);
        queue.push(right.left);
    }

    return true;
};

使用栈


function isSymmetric(root: TreeNode | null): boolean {
    if (!root) return true;

    const stack: TreeNode[] = [];

    stack.push(root.right);
    stack.push(root.left);

    while (stack.length) {
        const left = stack.pop();
        const right = stack.pop();

        if (!left && !right) {
            continue;
        }
        else if (!left || !right || left.val !== right.val) return false;

        stack.push(right.right);
        stack.push(left.left);
        stack.push(right.left);
        stack.push(left.right);
    }

    return true;
};

无需在意顺序


function isSymmetric(root: TreeNode | null): boolean {
    if (!root) return true;

    const stack: TreeNode[] = [];
		// 这里需要入栈left和right，两个两个拿出来对比
    stack.push(root.left);
    stack.push(root.right);

    while (stack.length) {
        const left = stack.pop();
        const right = stack.pop();

        if (!left && !right) {
            continue;
        }
        else if (!left || !right || left.val !== right.val) return false;

				// 这里的顺序就是内侧外侧对比的顺序
        stack.push(left.left);
        stack.push(right.right);
        stack.push(left.right);
        stack.push(right.left);
    }

    return true;
};