翻转二叉树
Invert Binary Tree
把二叉树的每个节点的左右子树互换，返回翻转后的根节点。
在力扣中练习题目描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3] 输出：[2,3,1]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
解题思路
主解法
递归 · 先交换再下探
当前节点换孩子，左右子树各自翻转
翻转一棵树，可以拆成三件事：交换当前节点的左右孩子、翻转左子树、翻转右子树。三件事互不影响，所以先交换还是先递归都可以。
分步图解
空节点直接返回；从根开始，先交换左右孩子，再递归处理两棵子树。
交换每个节点的左右孩子
递归到空节点时返回。交换后原来的左子树变成右子树，但节点本身和它的值没有变，只是左右关系对调。
分步图解
交换 5 的左右孩子：现在左边是 8，右边是 3。
交换每个节点的左右孩子
自拟树是一棵三层满二叉树，交换根之后递归顺序会先进入原来的右子树 8；画面上节点位置会左右移动，这是交换孩子后的真实布局，不是节点值变了。
时间 O(n)，每个节点访问一次；空间 O(h) 递归栈。
时间 O(n)空间 O(h) 递归栈
易错点
- 只交换根的孩子：子树内部没有翻转，结果只是左右两棵子树整体换位。
- 交换值而不是交换孩子：如果节点带额外字段或需要保持节点身份，会出错。
- 空树没有处理：递归进入空指针。
对照解法
层序 · 队列
每个出队节点都交换孩子，再把孩子入队
同样 O(n)，但需要 O(宽度) 队列；递归版更短，队列版避免深递归。
用队列遍历每个节点：出队时交换它的左右孩子，然后把（交换后的）左右孩子入队。因为每个节点都会被处理一次，整棵树自然完成镜像。
与递归版相比，它不依赖调用栈，适合树很深的情况；代价是队列可能同时保存一整层节点。
注意入队时用的是交换后的孩子，但两个孩子都会被入队，所以先入左还是先入右不影响最终结果。
- 1根节点入队。
- 2出队一个节点，交换它的左右孩子。
- 3把两个孩子入队。
- 4队列空时返回根。
时间 O(n)空间 O(宽度)
易错点
- 交换后只入队一个孩子：另一棵子树漏翻。
- 空树直接入队：队列里出现空指针。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
root = [5,3,8,2,4,7,9]空节点直接返回；从根开始，先交换左右孩子，再递归处理两棵子树。
交换每个节点的左右孩子
查看 C++ 代码
延伸阅读
- 翻转、镜像、对称判断都围绕“左右互换”这一个操作，可以先想清楚交换发生在递归前还是递归后。
- 交换左右孩子会改变中序遍历的结果；如果题目还要求保持 BST 性质，需要额外小心。