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;
}