翻转二叉树：一遍遍历交换左右

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。翻转二叉树是「二叉树基础」这一考点的代表题，也是练习"遍历时顺手改写结构"这种写法的好例子。它是经典训练题，不是真题，也不押题。

题目

给定一棵二叉树，把它左右镜像翻转：每个结点的左子树和右子树互换位置，翻转要递归地作用到整棵树的每一层，不只是根结点这一层。例如根 4、左子树 2(1,3)、右子树 7(6,9) 的树，翻转后应变成根 4、左子树 7(9,6)、右子树 2(3,1)——不仅根的左右孩子换了，两棵子树内部各自的左右孩子也都换了。设计算法完成这个翻转，返回翻转后的根结点。

这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——遍历一遍、每个结点顺手交换一次左右孩子，就是这道题要求的全部。

直观解法：递归遍历,顺手交换每个结点的左右孩子

「翻转」这个词已经把做法写在题面里了：每个结点的左右孩子要互换。那就递归地走遍整棵树，走到一个结点就把它的 left 和 right 交换一次，再递归处理交换后的两棵子树——因为翻转必须作用到每一层，光换根结点这一层是不够的。

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* invertTree(TreeNode *root) {
    if (root == NULL) return NULL;             // 空结点直接返回,递归自然终止

    TreeNode *temp = root->left;                 // 用临时变量交换左右孩子
    root->left  = root->right;
    root->right = temp;

    invertTree(root->left);                      // 递归翻转交换后的左子树
    invertTree(root->right);                      // 递归翻转交换后的右子树

    return root;
}

拿开头的例子走一遍：根 4 先交换左右孩子，变成左 7、右 2；接着递归翻转左子树（原来的 7 子树）——7 的左右孩子 6、9 互换，变成左 9、右 6；再递归翻转右子树（原来的 2 子树）——2 的左右孩子 1、3 互换，变成左 3、右 1。整棵树的先序遍历从 4 2 1 3 7 6 9 变成 4 7 9 6 2 3 1，每一层的左右关系都翻转了过来。

复杂度：每个结点只做一次常数时间的交换，时间 $O(n)$；递归栈深度等于树高，空间 $O(h)$。

为什么它就是满分解

这道题没有「暴力 vs 最优」的分差。用总纲的「找浪费三问」审一遍，三问全部答「没有」：

1. 有没有重复扫描？ 没有。每个结点只在自己那一层被访问一次，交换完就递归下去，不会回头再处理已经交换过的结点。
2. 有没有重算已知的东西？ 没有。交换操作本身就是最终结果的一部分，不存在"先算出某个中间值、之后再重新推导"的情况。
3. 有没有放着性质不用？ 没有。题目要的就是"每个结点的左右孩子互换"，递归遍历直接把这条要求落实到每一个结点，没有额外的结构性质可以利用。

更根本的一条：要把树上每个结点的左右孩子都换一遍，至少要把每个结点访问一次（少访问一个，那个结点的左右孩子就没翻转）——遍历一遍就是 $O(n)$ 的下界，任何正确算法都躲不开。碰到下界，直观写法即最优。

真正的难点在两处边界

分不在优化上，在把两处边界写对：

• 交换必须借助临时变量。TreeNode *temp = root->left 这一步不能省——如果直接写 root->left = root->right; root->right = root->left;，第二行读到的 root->left 已经被第一行覆盖成了原来的 root->right，交换结果是左右孩子都变成了原来的右孩子，原来的左子树整个丢失。这是"同时交换两个变量"的通用陷阱，翻转二叉树这道题会把它放大成"丢掉半棵子树"的严重错误。
• 空结点必须直接返回，不能继续往下访问。root == NULL 时如果不提前返回，后面 root->left 这样的访问会直接触发空指针错误。这一条同时也是递归能够正常终止的关键——每次递归调用的对象在变小（子树在变浅），碰到空结点就是最基础的情形，兜底之后递归才能收敛。

两处任何一处出错，代码要么在运行时直接崩溃（漏判空结点），要么"跑得动但翻转错了"（交换没用临时变量、丢了子树）——后一种错误尤其隐蔽，因为程序不会报错，只是结果不对。

递归交换左右孩子，看一遍

用根 4、左子树 2(1,3)、右子树 7(6,9) 的树演示翻转——注意每一层的左右孩子都被交换，不只是根结点这一层：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。驱动代码翻转后按先序打印结果 4,7,9,6,2,3,1——原来的左子树 2,1,3 整体挪到了右边，原来的右子树 7,6,9 整体挪到了左边，且各自内部的左右孩子也都换了。

别画蛇添足

这道题结构简单，过度设计的空间不大，但有两个常见的「想复杂了」：

• 想先算出整棵树再重新构造一份镜像树。用先序/中序遍历把原树的结构记录下来，再按镜像规则重新 malloc 出一整棵新树——这样不仅多了一倍的空间开销，还要处理"新树和原树对应关系"这类多余的映射逻辑。原地交换指针，一遍递归就地完成，不需要额外分配任何新结点。
• 纠结于"先交换再递归"还是"先递归再交换"哪个更快。两种写法的时间和空间复杂度完全一样——先交换再递归，是对交换后的两棵子树各自递归下去；先递归再交换，是先把两棵子树各自翻转好，最后再统一换个位置。都是每个结点访问一次、交换一次，选哪种纯粹是个人习惯，不存在效率上的优劣，不用为了"选出更优版本"而纠结。

下一步

• 在 OJ 上把代码提交跑一遍：翻转二叉树
• 看先序遍历的交互演示（翻转常配合先序观察结构变化）：先序遍历可视化
• 回到方法论源头：「暴力解到最优解」真题专题总纲

相关真题（21题）

2026Q42分2025Q32分2025Q42分2024Q32分2023Q52分2022Q32分2022Q52分2020Q32分2020Q92分2019Q22分2018Q42分2017Q42分2017Q52分2015Q22分2011Q42分2011Q62分2010Q32分2010Q62分2009Q32分2009Q52分2009Q62分