二叉树是否对称

算法思路

一棵二叉树对称，当且仅当它的左子树与右子树互为镜像。

递归比较一对节点 (t1, t2)：

• 两节点都为空 → 镜像
• 仅一方为空 → 非镜像
• 值不等 → 非镜像
• 否则递归比较 t1.left 与 t2.right、t1.right 与 t2.left

从根开始调用 is_mirror(root.left, root.right) 即可。空树视为对称。

也可用队列迭代：每次出队一对节点，按镜像关系把子节点成对入队。

时间 O(n)，空间 O(h)（递归）或 O(w)（队列，w 为最大层宽）。

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_symmetric(root: TreeNode) -> bool:
    def is_mirror(t1: TreeNode, t2: TreeNode) -> bool:
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        if t1.val != t2.val:
            return False
        return is_mirror(t1.left, t2.right) and is_mirror(t1.right, t2.left)

    return is_mirror(root.left, root.right) if root else True

js

function TreeNode(val, left, right) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
}

function isSymmetric(root) {
    function isMirror(t1, t2) {
        if (!t1 && !t2) return true;
        if (!t1 || !t2) return false;
        if (t1.val !== t2.val) return false;
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }

    return root ? isMirror(root.left, root.right) : true;
}

go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isMirror(root.Left, root.Right)
}

func isMirror(t1, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    if t1.Val != t2.Val {
        return false
    }
    return isMirror(t1.Left, t2.Right) && isMirror(t1.Right, t2.Left)
}