2026/7/9大约 4 分钟
LeetCode 226. 翻转二叉树
题目核心
给定一棵二叉树的根节点 root，将整棵树左右翻转，并返回翻转后的根节点。
翻转的意思是：每一个节点的左子树和右子树都要交换。
例如：
4 4
/ \ / \
2 7 -> 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1解题思考过程
第一步：理解问题
翻转二叉树的核心是交换每个节点的左右子树。
第二步：暴力解法（递归）
最直接的思路：递归处理每个节点，交换它的左右子树。
递归公式：
flipTree(root) = 交换 root.left 和 root.right，然后递归翻转左右子树
base case：如果 root 为空，返回 null第三步：验证递归过程
以示例树为例：
flipTree(4):
flipTree(2):
flipTree(1): 叶子节点，返回1
flipTree(3): 叶子节点，返回3
交换 1 和 3
返回 2（现在左是3，右是1）
flipTree(7):
flipTree(6): 叶子节点，返回6
flipTree(9): 叶子节点，返回9
交换 6 和 9
返回 7（现在左是9，右是6）
交换 2 和 7
返回 4（现在左是7，右是2）结果：
4
/ \
7 2
/ \ / \
9 6 3 1正确！
第四步：迭代解法（BFS/DFS）
递归可能会栈溢出（对于非常深的树），可以用迭代方式：
BFS：用队列存储待处理的节点
while 队列不为空:
取出节点
交换左右子树
如果左子树不为空，加入队列
如果右子树不为空，加入队列第五步：两种方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 递归 | O(n) | O(h) - h是树高度 | 代码简洁 |
| 迭代 | O(n) | O(n) - 队列最多n/2个节点 | 避免栈溢出 |
两种方法时间复杂度相同。
第六步：为什么这道题经典
这道题被称为"Google面试第一题"，因为它非常直观，但能考察递归思维。
递归的关键在于：先处理子问题，再处理当前问题。
当前解法：递归交换左右子树
当前代码使用递归，从当前节点开始交换左右子树，然后继续递归处理交换后的左右子树。
function TreeNode(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
var invertTree = function (root) {
if (root == null) {
return null;
}
let temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
};算法思想
翻转二叉树的核心操作只有一个：
交换当前节点的左孩子和右孩子但是只交换根节点还不够，因为根节点下面的每一个子节点也都需要被翻转。所以递归函数要做三件事：
- 如果当前节点是
null，直接返回。 - 交换当前节点的
left和right。 - 继续递归翻转当前节点的左右子树。
你的代码先交换当前节点，再递归左右子树，所以遍历顺序可以理解成：
当前节点 -> 左子树 -> 右子树也就是前序遍历的思路。
为什么交换后再递归也正确
交换之前：
root.left 是原来的左子树
root.right 是原来的右子树交换之后：
root.left 变成原来的右子树
root.right 变成原来的左子树这时候再执行：
invertTree(root.left);
invertTree(root.right);虽然左右位置已经换过了，但这两棵子树仍然都会被递归处理到。也就是说，原来的左子树和原来的右子树都不会丢失，只是处理顺序变了。
所以无论是：
先交换，再递归还是：
先递归，再交换本题都可以得到正确结果。区别只是遍历顺序不同。
递归终止条件
if (root == null) {
return null;
}当递归走到空节点时，说明这条路径已经到头了，不需要继续交换，直接返回 null。
这个条件非常重要，否则访问 root.left 或 root.right 时会报错。
单层递归做了什么
假设当前节点是 root：
let temp = root.left;
root.left = root.right;
root.right = temp;这三行代码完成左右子树交换：
- 先用
temp保存原来的左子树。 - 再把右子树放到左边。
- 最后把原来的左子树放到右边。
然后：
invertTree(root.left);
invertTree(root.right);继续处理当前节点下面的两棵子树。每一层递归都重复这个动作，整棵树就被翻转了。
复杂度
- 时间复杂度：
O(n) - 空间复杂度：
O(h)
其中 n 是二叉树节点数量，h 是二叉树高度。
每个节点都会被访问一次，所以时间复杂度是 O(n)。
空间复杂度来自递归调用栈。在最坏情况下，二叉树退化成链表，h = n；在平衡二叉树中，h = log n。