Appearance
翻转二叉树：一遍遍历交换左右
本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。翻转二叉树是「二叉树基础」这一考点的代表题，也是练习"遍历时顺手改写结构"这种写法的好例子。它是经典训练题，不是真题，也不押题。
题目
给定一棵二叉树，把它左右镜像翻转：每个结点的左子树和右子树互换位置，翻转要递归地作用到整棵树的每一层，不只是根结点这一层。例如根 4、左子树 2(1,3)、右子树 7(6,9) 的树，翻转后应变成根 4、左子树 7(9,6)、右子树 2(3,1)——不仅根的左右孩子换了，两棵子树内部各自的左右孩子也都换了。设计算法完成这个翻转，返回翻转后的根结点。
这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——遍历一遍、每个结点顺手交换一次左右孩子，就是这道题要求的全部。
直观解法：递归遍历,顺手交换每个结点的左右孩子
「翻转」这个词已经把做法写在题面里了：每个结点的左右孩子要互换。那就递归地走遍整棵树，走到一个结点就把它的 left 和 right 交换一次，再递归处理交换后的两棵子树——因为翻转必须作用到每一层，光换根结点这一层是不够的。
c
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，每一层的左右关系都翻转了过来。
复杂度：每个结点只做一次常数时间的交换，时间
为什么它就是满分解
这道题没有「暴力 vs 最优」的分差。用总纲的「找浪费三问」审一遍，三问全部答「没有」：
- 有没有重复扫描？ 没有。每个结点只在自己那一层被访问一次，交换完就递归下去，不会回头再处理已经交换过的结点。
- 有没有重算已知的东西？ 没有。交换操作本身就是最终结果的一部分，不存在"先算出某个中间值、之后再重新推导"的情况。
- 有没有放着性质不用？ 没有。题目要的就是"每个结点的左右孩子互换"，递归遍历直接把这条要求落实到每一个结点，没有额外的结构性质可以利用。
更根本的一条：要把树上每个结点的左右孩子都换一遍，至少要把每个结点访问一次（少访问一个，那个结点的左右孩子就没翻转）——遍历一遍就是
真正的难点在两处边界
分不在优化上，在把两处边界写对：
- 交换必须借助临时变量。
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出一整棵新树——这样不仅多了一倍的空间开销，还要处理"新树和原树对应关系"这类多余的映射逻辑。原地交换指针，一遍递归就地完成，不需要额外分配任何新结点。 - 纠结于"先交换再递归"还是"先递归再交换"哪个更快。两种写法的时间和空间复杂度完全一样——先交换再递归，是对交换后的两棵子树各自递归下去；先递归再交换，是先把两棵子树各自翻转好，最后再统一换个位置。都是每个结点访问一次、交换一次，选哪种纯粹是个人习惯，不存在效率上的优劣，不用为了"选出更优版本"而纠结。
下一步
- 看先序遍历的交互演示（翻转常配合先序观察结构变化）：先序遍历可视化
- 回到方法论源头：「暴力解到最优解」真题专题总纲