对称二叉树 图解题解

这道题真正在问什么

题目给一棵二叉树，问它是否关于根节点这条中轴左右镜像对称。注意「对称」不等于「左右子树长得一样」：想象把树沿中轴对折，左半边最外侧的节点要正好压在右半边最外侧的节点上。题目示例 [1,2,2,null,3,null,3] 里，两棵子树都是「2 带一个右孩子 3」，长得一模一样，答案却是 false——对折之后两个 3 的位置根本对不上。要判断的是位置加数值的双重对应。

为什么直接比较左右子树行不通

最直觉的做法是逐层取出节点检查每层是否回文，可行但要小心补 null 占位，写起来啰嗦。更本质的观察是：整棵树对称，当且仅当左子树与右子树互为镜像。而镜像的含义是外侧对外侧、内侧对内侧——照镜子时，左子树的最外缘正对右子树的最外缘。所以比较必须交叉进行：左边节点的左孩子，要去和右边节点的右孩子配对。这一步交叉是全题的题眼，也是它区别于「判断两棵树是否相同」的地方。

递归函数为什么要同时带两个节点

单参数的递归表达不了「这棵子树和另一棵子树互为镜像」这种跨树关系，所以要定义双参数函数 mirror(a, b)，含义是「以 a、b 为根的两棵子树互为镜像」，入口调用 mirror(root.left, root.right)。它的子问题结构和自身完全一致：a 与 b 镜像，等价于两者值相等，且 a.left 与 b.right 镜像、a.right 与 b.left 镜像。问题规模每递归一层就缩小到下一层的镜像对，天然收敛。

三个判断条件为什么缺一不可

递归里按顺序判三种情况：a、b 都为空返回 true——对折后两边都没有东西，天然对齐，这是递归的触底出口；一空一有返回 false——结构已经错位，这是只比较数值时最容易漏掉的情况；值不相等返回 false。三关都过了，才继续往里递归两组镜像对。正确性来自「处处相等」：任何一对镜像位置不匹配，false 会沿递归链一路短路传回根部，整棵树即判不对称。

复杂度怎么算，哪些边界会翻车

时间 O(n)：每个节点至多参与一次镜像比较，n 为节点数。空间 O(h)：递归栈深等于树高，平衡树约 O(log n)，退化成链最坏 O(n)。最常见的错误是把递归写成 mirror(a.left, b.left)——不交叉，验证的就是「左右子树相同」而非镜像；其次是只比完根的左右孩子就下结论，上层对称不代表深层对称，必须递归到底。空树按约定返回 true。

Java

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;          // 空树对称
        return mirror(root.left, root.right);   // 判左右子树互为镜像
    }
    private boolean mirror(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;   // 都空 → 对称
        if (a == null || b == null) return false;  // 一空一有 → 不对称
        if (a.val != b.val) return false;          // 值不等 → 不对称
        return mirror(a.left, b.right)             // 外侧对外侧
            && mirror(a.right, b.left);            // 内侧对内侧
    }
}

Python

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True
        def mirror(a, b):
            if a is None and b is None:        # 都空 → 对称
                return True
            if a is None or b is None:         # 一空一有 → 不对称
                return False
            if a.val != b.val:                 # 值不等 → 不对称
                return False
            return mirror(a.left, b.right) \
                and mirror(a.right, b.left)    # 外⟷外、内⟷内
        return mirror(root.left, root.right)

C++

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return mirror(root->left, root->right);
    }
private:
    bool mirror(TreeNode* a, TreeNode* b) {
        if (a == nullptr && b == nullptr) return true;   // 都空 → 对称
        if (a == nullptr || b == nullptr) return false;  // 一空一有 → 不对称
        if (a->val != b->val) return false;              // 值不等 → 不对称
        return mirror(a->left, b->right)                 // 外侧对外侧
            && mirror(a->right, b->left);                // 内侧对内侧
    }
};