LeetCode 101. 对称二叉树

◎

本节目标

用双节点镜像递归，同时比较两棵应当互为镜像的子树。

这道题沿用子树信息与递归判断的合并思路，但递归接口同时接收左右两棵子树。

查看 LeetCode 原题

题意与边界

一棵树对称，要求根的左右子树在结构和节点值上互为镜像。两棵空树彼此镜像；只有一棵为空时立即不对称。空树本身也满足对称定义。

镜像双节点接口

定义 mirror(left, right) 表示两棵给定子树是否镜像。根值相同还不够：必须把 left.left 与 right.right 配对，把 left.right 与 right.left 配对。这样的交叉递归同时检查结构位置和节点值，能识别“值相同但结构方向相同”的反例。

正确性依据

若两棵子树均为空，它们显然镜像；若只有一棵为空或值不同，则不可能镜像。其余情况下，当前两根相等，且两组交叉子树分别镜像时，整棵子树镜像。递归覆盖所有对应位置，因此 mirror 的结果与镜像定义完全一致。

代码实现

C++

C++17

class Solution {
private:
    bool mirror(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) {
            return true;
        }
        if (left == nullptr || right == nullptr || left->val != right->val) {
            return false;
        }
        return mirror(left->left, right->right) && mirror(left->right, right->left);
    }

public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        return mirror(root->left, root->right);
    }
};

Python

Python 3

from typing import Optional


class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
            if left is None and right is None:
                return True
            if left is None or right is None or left.val != right.val:
                return False
            return mirror(left.left, right.right) and mirror(left.right, right.left)

        if root is None:
            return True
        return mirror(root.left, root.right)

复杂度分析

每个节点最多参与一次配对比较，时间复杂度为 O(n)。递归栈深度为树高 h，额外空间为 O(h)。

易错点

• 比较 left.left 与 right.left，这检查的是同方向结构而不是镜像结构。
• 只比较同层节点值，遗漏一侧缺失节点的结构差异。
• 把空树判为不对称，违背镜像关系的基例。

模式迁移

双节点递归也适用于比较两棵树是否相同、判断翻转后的结构关系等问题。关键是先写清两组参数的对应规则，再递归到下一层。