题目

解法：递归镜像

思路

采用递归方式比较左右子树是否互为镜像，核心是同时遍历对称位置的节点。

该方法正确性基于对称二叉树的定义：若一棵树与其镜像相同，则对称。递归过程中保持不变量——对于任意对称节点对(p,q)，必须满足值相等且p的左子树与q的右子树对称、p的右子树与q的左子树对称。基础情况（两空节点）成立，递归步骤确保局部对称性传递到整体，不会遗漏任何需要比较的节点对。

• Step 1: 定义辅助函数check(p, q)判断两子树是否镜像
• Step 2: 边界处理：双空返回true，单空返回false
• Step 3: 递归检查值相等且交叉子树对称
• Step 4: 主函数调用check(root->left, root->right)

复杂度

• 时间复杂度: $O(n)$，其中n为节点数，每个节点仅访问一次
• 空间复杂度: $O(h)$，其中h为树高，递归栈空间消耗

代码

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }
};