c++中如何实现二叉树的镜像反转_c++递归实现树结构变换【详解】

二叉树镜像反转是将每个节点的左、右子树指针互换。递归实现应先递归处理左右子树再交换指针，终止条件为根为空；推荐用std::swap保证安全简洁；时间复杂度O(n)，空间复杂度O(h)。

什么是二叉树镜像反转

二叉树镜像反转，就是把每个节点的左子树和右子树互换。不是“翻转值”，而是交换指针指向——root->left 和 root->right 的引用关系对调。递归是最自然的实现方式，因为每个子树都遵循相同规则。

核心递归逻辑怎么写

关键在于：先递归处理左右子树，再交换它们；或者先交换再递归——两种顺序都可行，但前者更符合“自底向上”的直观理解，也避免空指针误操作。

常见错误是只交换当前层、忘了递归下去，导致只有根节点被翻转。

• 递归终止条件必须是 root == nullptr
• 不能只写 swap(root->left, root->right) 就结束，否则子树内部结构不变
• 推荐顺序：递归左子树 → 递归右子树 → 交换左右指针

void mirror(TreeNode* root) {
    if (!root) return;
    mirror(root->left);
    mirror(root->right);
    std::swap(root->left, root->right);
}

为什么用 std::swap 而不是手动赋值

手动写 TreeNode* tmp = root->left; root->left = root->right; root->right = tmp; 没问题，但易错且冗余。而 std::swap 是标准、安全、可读性强的选择。

注意：如果节点指针类型是 unique_ptr 或 shared_ptr，std::swap 同样适用，且会正确转移所有权或引用计数。

• 用 std

  

  ::swap 可避免临时变量命名污染和漏赋值
• 编译器对 std::swap 有优化，不会额外拷贝对象
• 若自己实现 swap，需确保异常安全（移动语义下尤其重要）

非递归版本要不要考虑

可以，但没必要作为首选。镜像反转本质是后序遍历变体，递归简洁清晰；强行改迭代会引入显式栈和状态标记，代码复杂度陡增，还容易在“交换时机”上出错。

只有在明确禁止递归（如嵌入式栈空间极小）、或需要与其它遍历复用同一栈结构时，才值得投入精力写迭代版。

真正容易被忽略的是：镜像操作本身不改变节点内存布局，也不释放/新建节点，所以时间复杂度 O(n)、空间复杂度 O(h)（h 是树高，即递归栈深），最坏情况退化为链表时是 O(n)。