c++中如何判断二叉树是否是对称的_c++镜像二叉树判断算法

判断二叉树是否对称需递归或迭代检查左右子树是否镜像相等：即左子树左孩子与右子树右孩子、左子树右孩子与右子树左孩子分别相等且值相同；常见错误是误判子树各自对称或忽略空指针和节点值校验。

用递归比较左右子树是否互为镜像

判断二叉树是否对称，本质是检查左子树是否与右子树“镜像相等”：即左子树的左孩子等于右子树的右孩子，左子树的右孩子等于右子树的左孩子。不能只比结构，必须同步比较节点值。

关键点在于设计一个辅助函数 isMirror(TreeNode* left, TreeNode* right)，它接收两个子树根节点，返回它们是否互为镜像：

• 都为空 → 对称（return true）
• 仅一个为空 → 不对称（return false）
• 都不为空但值不等 → 不对称（return false）
• 都不为空且值相等 → 递归检查 left->left 与 right->right，以及 left->right 与 right->left

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    return isMirror(root->left, root->right);
}
bool isMirror(TreeNode left, TreeNode right) {
if (!left && !right) return true;
if (!left || !right) return false;
if (left->val != right->val) return false;
return isMirror(left->left, right->right) && 
isMirror(left->right, right->left);
}

迭代写法：用栈模拟递归配对检查

递归直观但有栈溢出风险；迭代更可控，核心是把“待比较的节点对”压入栈中，每次弹出一对做值比较，再把下一层的镜像组合推入栈。

初始压入 root->left 和 root->right；每次取两个节点 l 和 r：

• 都为空 → 继续下一轮
• 仅一个为空 → 返回 false
• 值不等 → 返回 false
• 值相等 → 将 l->left 与 r->right、l->right 与 r->left 成对压栈

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    stack stk;
    stk.push(root->left);
    stk.push(root->right);
    while (!stk.empty()) {
        TreeNode* r = stk.top(); stk.pop();
        TreeNode* l = stk.top(); stk.pop();
        if (!l && !r) continue;
        if (!l || !r) return false;
        if (l->val != r->val) return false;
        stk.push(l->left);  stk.push(r->right);
        stk.push(l->right); stk.push(r->left);
    }
    return true;
}

常见错误：误用“左右子树各自对称”逻辑

新手常写成：isSymmetric(root->left) && isSymmetric(root->right) —— 这是在检查“左子树自身对称”且“右子树自身对称”，完全偏离题意。对称性是跨左右子树的镜像关系，不是子树内部性质。

另一个典型错误是只比结构忽略值：比如用 nullptr 占位但没校验 val，导致 [1,2,2,null,3,null,3] 被误判为对称（实际不是，因为两个 3 不在镜像位置）。

测试时务必覆盖这些用例：

• [1,2,2,3,4,4,3] → true
• [1,2,2,null,3,null,3] → false（注意 null 的位置）
• [1] → true
• [] → true

时间与空间复杂度差异明显

递归和迭代都是 O(n) 时间复杂度，每个节点访问一次。但空间表现不同：

• 递归：最坏深度 O(n)（退化为链表），平均 O(h)（h 为树高）
• 迭代：栈中最多存 O(w) 个节点（w 为最大宽度），对于满二叉树，宽度远小于深度，此时迭代更省内存

如果题目明确要求“避免递归”或输入可能极深，优先选迭代；否则递归更易写对、不易漏边界。

真正容易被忽略的是空指针解引用——无论递归还是迭代，必须在取 ->val 或访问子指针前，先判断指针非空。漏掉这一层检查，本地能过但线上 runtime error 是高频翻车点。