C++如何实现二叉树的镜像翻转(原地左右子节点递归交换)-C++-PHP中文网

镜像翻转需后序遍历递归交换左右指针：先递归处理左右子树，再交换当前节点的left和right指针，确保不重复或遗漏；错误写法是先交换后递归，会导致两次递归进入同一子树。

c++如何实现二叉树的镜像翻转(原地左右子节点递归交换)

镜像翻转就是递归交换左右子树

直接对每个节点调用 swap 交换其 left 和 right 指针，递归到底层再逐层返回。这不是创建新树，而是原地修改指针指向——所有操作都在原有节点上完成，不分配新节点内存。

关键点在于：必须先递归处理子树，再交换当前节点的左右指针；如果先交换再递归，会导致后续递归进错分支（比如原左子树已被换到右位置，递归时可能重复处理或漏掉）。

递归终止条件是 root == nullptr
交换操作写在递归调用之后（后序遍历逻辑）
函数返回值通常为 void，因为只改指针，不依赖返回值重建树

C++实现中容易写成前序导致逻辑错误

常见错误是把 swap 放在递归调用之前，即先交换再递归：

void mirrorTree(TreeNode* root) {
    if (!root) return;
    swap(root->left, root->right); // ❌ 错：此时 left/right 已交换，下面两个递归都进了“新右子树”
    mirrorTree(root->left);         // 实际递归的是原 right 子树
    mirrorTree(root->right);       // 再次递归原 right 子树（因为 left 已被换走）
}

正确写法必须保证两次递归分别进入原始的左、右子树：

void mirrorTree(TreeNode* root) {
    if (!root) return;
    mirrorTree(root->left);   // ✅ 先递归原左子树
    mirrorTree(root->right);  // ✅ 再递归原右子树
    swap(root->left, root->right); // ✅ 最后交换，不影响递归路径
}

非递归写法要用 stack 模拟后序遍历

想避免递归栈溢出（比如极深偏斜树），就得用显式栈。但注意：不能用简单 BFS 或前序迭代，必须保证「子树处理完才交换」，否则又会复现上面的逻辑错。

C++14

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

下载

推荐做法是用栈存节点，配合一个 visited 标记（或用 pair 表示是否已处理子树），或者更简洁地——先压入右子、再左子，但交换动作延后到第二次访问时做。实际工程中若真遇到栈深问题，往往说明树结构异常，优先检查建树逻辑更实际。

迭代版本代码量翻倍，且易引入状态管理 bug
std::stack 存指针即可，不需要复制节点
若用 queue 做层序然后每层 swap，也能实现，但那是广度优先镜像，和题目要求的“递归交换”语义不同

TreeNode 定义和边界情况必须手动验证

LeetCode 风格的 TreeNode 通常长这样：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

测试时别忘了这几个 case：