C++如何实现二叉树的镜像左右翻转(原地变换)-C++-PHP中文网

原地翻转指不新建节点、仅交换各节点left/right指针实现二叉树镜像，时间复杂度o(n)，空间复杂度o(h)；递归需先递归子树再交换，迭代需先交换再入栈。

c++如何实现二叉树的镜像左右翻转(原地变换)

什么是“原地翻转”？先看关键判断

所谓原地翻转，就是不新建节点、不额外分配树结构内存，只通过交换每个节点的 left 和 right 指针完成。核心在于：所有操作必须在原有节点引用上进行，时间复杂度 O(n)，空间复杂度仅递归栈 O(h)（h 为树高）。

递归实现：最直观但要注意空指针和调用顺序

递归写法简洁，但容易在两个地方出错：一是没判空直接访问 left/right，二是交换时机不对导致子树被覆盖。

必须先递归处理左右子树，再交换当前节点的指针；如果先交换再递归，会把原 left 子树当成右子树去处理，逻辑错乱
入口函数需判空：若传入根节点为 nullptr，直接返回，否则访问 nullptr->left 会崩溃
典型错误写法：root->left = mirrorTree(root->right); root->right = mirrorTree(root->left); —— 第二行的 root->left 已是翻转后的新左子树，不是原来的左子树

正确写法示例：

TreeNode* mirrorTree(TreeNode* root) {
    if (!root) return nullptr;
    TreeNode* left = mirrorTree(root->left);
    TreeNode* right = mirrorTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

迭代实现：用栈模拟递归，避免栈溢出风险

当树深度很大（比如退化成链表，h ≈ n），递归可能触发栈溢出。此时用显式栈更稳妥，且能清晰控制遍历顺序。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

推荐用 stack<treenode></treenode>，每次 pop 一个节点，交换其 left/right，再将非空子节点 push 进栈
注意：必须先 push left 再 push right（或反过来），否则遍历顺序不同，但翻转结果不受影响；真正关键的是——交换动作必须在 push 之前做
不能写成 “先 push 子节点，再交换”，那样交换的是下一层节点，当前层没动

简明迭代版本：

TreeNode* mirrorTree(TreeNode* root) {
    if (!root) return nullptr;
    stack<treenode> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        swap(node->left, node->right);
        if (node->left) stk.push(node->left);
        if (node->right) stk.push(node->right);
    }
    return root;
}</treenode>