题目描述
给你一棵二叉树的根节点 root ，请你翻转这棵二叉树，并返回其根节点。
所谓“翻转二叉树”，就是把每个节点的左子树和右子树交换。
比如原来的树是：
4
/ \
2 7
/ \ / \
1 3 6 9
翻转之后会变成：
4
/ \
7 2
/ \ / \
9 6 3 1
也就是说，整棵树中的每一个节点，都要把左右孩子交换一下。
解题思路
这道题是一道非常经典的二叉树题目。
题目本身不复杂，它真正的核心其实只有一句话：
遍历整棵树，把每个节点的左孩子和右孩子交换。
所以这道题无论你是用：
-
递归
-
迭代
本质都一样，只是“遍历树”的方式不同而已。
你给出的正好是这道题最常见的两种写法：
-
递归写法
-
栈模拟 DFS 的迭代写法
下面分别来讲。
方法一：递归解法
代码
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode tmp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(tmp);
return root;
}
}
递归思路
递归写法非常符合这道题的定义。
对于任意一个节点 root：
-
先翻转它的右子树
-
再翻转它原来的左子树
-
最后把它们交换过来
也可以理解成：
-
当前节点要翻转
-
那它的左右子树也都必须先各自翻转好
-
然后再挂回相反的位置
这正是递归最适合处理的结构。
为什么递归能做这题
因为二叉树天然具有“子问题结构”：
一棵树的翻转，可以拆成“左子树翻转 + 右子树翻转 + 当前节点交换”。
也就是说：
-
大问题：翻转整棵树
-
小问题：翻转左子树、翻转右子树
而左子树和右子树本身又是二叉树，所以可以继续递归处理。
代码解析
1. 递归终止条件
if (root == null) return null;
如果当前节点为空，说明已经递归到叶子节点下面了，直接返回 null。
这是二叉树递归最基本的边界条件。
2. 先保存原来的左子树
TreeNode tmp = root.left;
因为后面要修改 root.left，所以必须先把原来的左子树保存下来。
不然一旦先改掉，就找不到原来的左子树了。
3. 左子树改成“翻转后的右子树”
root.left = invertTree(root.right);
这里先递归翻转右子树，然后把结果挂到左边。
4. 右子树改成“翻转后的原左子树”
root.right = invertTree(tmp);
因为原来的左子树已经保存在 tmp 里，所以这里递归翻转它，再挂到右边。
5. 返回当前节点
return root;
表示以当前节点为根的整棵子树已经翻转完成。
递归执行过程示例
我们以这棵树为例：
4
/ \
2 7
/ \ / \
1 3 6 9
处理根节点 4 时：
-
保存左子树
2 -
递归翻转右子树
7 -
再递归翻转左子树
2 -
最后交换位置
先翻转节点 7
7
/ \
6 9
翻转后：
7
/ \
9 6
再翻转节点 2
2
/ \
1 3
翻转后：
2
/ \
3 1
最后挂回根节点 4
得到：
4
/ \
7 2
/ \ / \
9 6 3 1
递归写法的特点
优点：
-
代码非常简洁
-
特别符合树的定义
-
很容易写出来
缺点：
-
依赖系统递归栈
-
如果树特别深，可能会有栈溢出的风险
方法二：迭代解法
代码
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null) stack.add(node.left);
if (node.right != null) stack.add(node.right);
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
}
return root;
}
}
迭代思路
迭代写法本质上也是在遍历整棵树，只不过它不依赖递归，而是自己手动用一个栈来模拟深度优先搜索（DFS）。
整体流程很简单：
-
先把根节点压栈
-
每次弹出一个节点
-
交换这个节点的左右孩子
-
再把它的左右孩子压栈，继续处理
-
直到栈为空
这样整棵树的每个节点都会被访问一次，每个节点的左右子树都会被交换一次。
代码解析
1. 判空
if (root == null) return null;
如果树为空，直接返回。
2. 初始化栈
Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
把根节点先放进栈里，作为 DFS 的起点。
这里用的是匿名内部类初始化写法，本质上就是把 root 先压进去。
如果写得更普通一点，也可以写成：
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
效果一样。
3. 不断弹出节点
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
每次从栈中取出一个节点进行处理。
4. 把左右孩子压栈
if (node.left != null) stack.add(node.left);
if (node.right != null) stack.add(node.right);
把当前节点的左右孩子加入栈中，后面继续处理它们。
这里注意一点：
是先把孩子压栈，再交换当前节点的左右孩子。
这么写完全没问题，因为无论先压栈还是先交换，只要压进去的是原来的两个子节点对象，后面都能继续遍历到。
5. 交换左右子树
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
这三句就是翻转当前节点的核心操作。
6. 返回根节点
return root;
整棵树处理完成后，返回根节点。
迭代执行过程示例
还是以这棵树为例：
4
/ \
2 7
/ \ / \
1 3 6 9
初始：
stack = [4]
第一次弹出 4
交换 4 的左右孩子：
4
/ \
7 2
然后把原来的左右孩子压栈。
第二次弹出 7
交换 7 的左右孩子：
7
/ \
9 6
第三次弹出 2
交换 2 的左右孩子：
2
/ \
3 1
继续处理剩下的叶子节点时，因为它们左右孩子都为空，所以交换后没有变化。
最终整棵树就翻转完成了。
两种方法的本质
无论是递归还是迭代，这道题都在做同一件事：
访问每一个节点，并交换它的左孩子和右孩子。
区别只在于遍历方式不同：
-
递归：依赖函数调用栈
-
迭代：手动维护一个显式栈
所以你可以把这题理解成一道“树的遍历题”，而不是复杂的构造题。
两种方法对比
递归写法
优点：
-
写法最简洁
-
最符合树的递归定义
-
面试中很常见
缺点：
-
依赖系统栈
-
树很深时可能爆栈
迭代写法
优点：
-
不依赖递归
-
更适合特别深的树
缺点：
-
代码稍长一些
-
需要自己维护栈
复杂度分析
设二叉树有 n 个节点。
时间复杂度
两种方法都是：
O(n)
因为每个节点都只会被访问一次。
空间复杂度
递归
O(h)
其中 h 是树的高度。 最坏情况下，如果树退化成链表，空间复杂度是 O(n)。
迭代
O(n)
最坏情况下，栈中可能会存放较多节点。
如果从树高角度分析，平均也和树结构有关。
为什么这题这么经典
这道题本身并不难，但它几乎成了二叉树题的“入门代表题”。
因为它能很好地练习这些基础能力：
-
是否理解二叉树递归
-
是否会写树的 DFS
-
是否能正确交换指针
-
是否知道递归和迭代的对应关系
所以虽然题目简单，但非常适合拿来打牢树的基本功。
总结
这道题的核心其实就一句话：
遍历整棵树，把每个节点的左右孩子交换。
对应到实现上：
-
递归写法：先递归翻转左右子树，再交换位置
-
迭代写法：用栈遍历整棵树，访问到一个节点就交换一次
所以你可以把这题记成一类非常典型的树题：
树的每个节点做相同操作，然后递归 / 迭代处理整棵树。
