361 lines
11 KiB
Markdown
361 lines
11 KiB
Markdown
---
|
||
tags: ["LeetCode", "二叉树", "深度优先搜索", "广度优先搜索", "递归", "迭代", "简单"]
|
||
create time: 2026-05-17 10:45
|
||
---
|
||
|
||
# 38-翻转二叉树
|
||
|
||
## 题面
|
||
|
||
给你一棵二叉树的根节点 `root`，**翻转**这棵二叉树，并返回其根节点。
|
||
|
||
> [!question] 💡 什么是「翻转」？
|
||
> 翻转的意思是：**交换每个节点的左右子树**。换句话说，把整棵树沿中线做一面镜子，左变右、右变左。
|
||
>
|
||
> > [!note] 🪞 直观理解
|
||
> > - 叶子节点：没有子节点，翻转后不变
|
||
> > - 中间节点：左右子树互换位置
|
||
> > - 翻转作用于**每一个**节点，从根一直到底
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：root = [4,2,7,1,3,6,9]
|
||
输出：[4,7,2,9,6,3,1]
|
||
|
||
原始树 翻转后
|
||
4 4
|
||
/ \ / \
|
||
2 7 → 7 2
|
||
/ \ / \ / \ / \
|
||
1 3 6 9 9 6 3 1
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：root = [2,1,3]
|
||
输出：[2,3,1]
|
||
|
||
2 2
|
||
/ \ → / \
|
||
1 3 3 1
|
||
```
|
||
|
||
**示例 3：**
|
||
|
||
```
|
||
输入：root = []
|
||
输出：[]
|
||
空树翻转后仍是空树
|
||
```
|
||
|
||
**约束：**
|
||
|
||
- 树中节点数目范围在 `[0, 100]` 内
|
||
- `-100 <= Node.val <= 100`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
### 方法一：深度优先搜索 DFS（递归）⭐⭐
|
||
|
||
#### 核心洞察
|
||
|
||
> [!question] 🤔 思考
|
||
> 如果你手里拿着一个节点，要翻转以它为根的这棵子树，你最需要做的动作是什么？
|
||
|
||
答案其实只有一个：**交换它的左右孩子**——就这么简单！
|
||
|
||
但要注意，交换完之后，左右孩子本身可能还挂着更深的子树，所以还需要**递归地对它们的子树也做同样的操作**。
|
||
|
||
这就是分而治之的思想：把「翻转整棵树」分解为「翻转每棵子树」，每个子树只做一件事——交换左右孩子。
|
||
|
||
#### 递归三要素
|
||
|
||
| 要素 | 内容 |
|
||
|------|------|
|
||
| **终止条件** | 节点为空时，直接返回（空树无需翻转） |
|
||
| **执行动作** | 交换 `node.Left` 和 `node.Right` |
|
||
| **递归调用** | 对交换后的左右子节点分别递归翻转 |
|
||
|
||
#### 执行流程图解
|
||
|
||
以示例 1 的原始树为例，展示递归如何逐层深入、逐层完成翻转：
|
||
|
||
```
|
||
4 4 4
|
||
/ \ / \ / \
|
||
2 7 → 7 2 → 7 2
|
||
/ \ / \ / \ / \ / \ / \
|
||
1 3 6 9 9 6 3 1 9 6 3 1
|
||
↑ ↑ ↑
|
||
步骤3 步骤2 步骤1
|
||
(叶子不变) (7的孩⼦换位置) (根节点先换⼿)
|
||
|
||
⾃顶向下递归（前序）：先交换再递归孩⼦
|
||
```
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
S["dfs(4)\n先交换 4 的孩⼦"] --> L["dfs(7)\n交换 7 的孩⼦"]
|
||
L --> L1["dfs(nil) → nil\n⽆需翻转"]
|
||
L --> R1["dfs(nil) → nil\n⽆需翻转"]
|
||
L1 --> L2["返回 {6, 3}\n7的孩⼦已翻转✅"]
|
||
R1 --> L2
|
||
L2 --> M["dfs(2)\n交换 2 的孩⼦"]
|
||
M --> L3["dfs(9)\n返回{6, nil}✅"]
|
||
M --> R2["dfs(nil) → nil\n返回{3}✅"]
|
||
L3 --> M2["返回{1,3}\n2的孩⼦已翻转✅"]
|
||
R2 --> M2
|
||
M2 --> E["dfs(4)\n左=翻转后{7}, 右=翻转后{2}\n根节点完成✅🎉"]
|
||
|
||
style E fill:#d4edda,stroke:#28a745,stroke-width:3px
|
||
style M fill:#cce5ff,stroke:#004085
|
||
style L fill:#fff3cd,stroke:#856404
|
||
```
|
||
|
||
#### Go 语言的优雅写法
|
||
|
||
Go 支持多值赋值，可以直接用一行完成交换，无需临时变量：
|
||
|
||
```go
|
||
// ❌ 常规写法（需要临时变量）
|
||
tmp := node.Left
|
||
node.Left = node.Right
|
||
node.Right = tmp
|
||
|
||
// ✅ Go 风格（并行交换）
|
||
node.Left, node.Right = node.Right, node.Left
|
||
```
|
||
|
||
> [!tip] 🔑 多值赋值的奥秘
|
||
> Go 的多值赋值是**先求值再赋值**——等号右边的表达式全部计算完毕后，再同时赋给左边。这意味着 `node.Left, node.Right = node.Right, node.Left` 等价于先用临时变量交换，不会先覆盖再出错。
|
||
|
||
#### 一步到位版（最简递归）
|
||
|
||
既然交换完左右子节点后，我们只需要让它们各自被翻转，那就可以把递归调用写在等号右边，直接赋值回去：
|
||
|
||
```
|
||
invertTree(node):
|
||
if node == nil: return nil
|
||
|
||
// 递归结果直接作为新的左右孩子
|
||
node.Left = invertTree(node.Right) // 原来的右子树翻转变左
|
||
node.Right = invertTree(node.Left) // 原来的左子树翻转变右
|
||
|
||
return node
|
||
```
|
||
|
||
> [!warning] ⚠️ 这和显式交换等价吗？
|
||
> **完全等价！** 注意 Go 多值赋值的特性：`node.Left = invertTree(node.Right)` 执行时，`node.Left` 的值已经作为参数传入右侧函数了，虽然这里我们把 `node.Right` 的返回值赋给了 `node.Left`……等等，这里似乎有问题？
|
||
>
|
||
> 实际上这种写法**有 bug**！第一行执行完后 `node.Left` 已经被修改了，第二行 `invertTree(node.Left)` 翻转的是新左子树而非原左子树。
|
||
>
|
||
> 正确的单行写法是用 Go 多值赋值：
|
||
|
||
```go
|
||
node.Left, node.Right = invertTree(node.Right), invertTree(node.Left)
|
||
```
|
||
|
||
> [!note] ⚡ 多值赋值的正确用法
|
||
> 上面的两行依次赋值写法是错误的（除非你确认左侧递归不依赖原值），但在 Go 中以下写法是正确的——因为多值赋值的右侧先全部求值完毕：
|
||
>
|
||
> ```go
|
||
> node.Left, node.Right = invertTree(node.Right), invertTree(node.Left)
|
||
> ```
|
||
>
|
||
> 这是最简洁的「翻转+递归+返回」三合一写法。
|
||
|
||
### 方法二：广度优先搜索 BFS（层序遍历迭代）⭐
|
||
|
||
#### 核心思想
|
||
|
||
BFS 按层访问节点。**对于每一层的每个节点，交换其左右孩子即可。**
|
||
|
||
这种方式的优点是过程非常直观：从左到右、从上到下扫一遍，每到一课就翻一次。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["第 1 层: [4]\n交换 4 的左右孩子"] --> B["第 2 层: [7,2]\n交换 7 和 2 的孩子"]
|
||
B --> C["第 3 层: [9,6,3,1]\n都是叶子,交换无变化"]
|
||
C --> D["遍历结束 ✅\n返回 root"]
|
||
|
||
style A fill:#e8f5e9
|
||
style B fill:#fff3e0
|
||
style C fill:#e3f2fd
|
||
style D fill:#fce4ec
|
||
```
|
||
|
||
#### 算法骨架
|
||
|
||
```
|
||
if root == nil: return nil
|
||
|
||
queue = [root]
|
||
|
||
while queue 非空:
|
||
node = pop(queue)
|
||
swap(node.left, node.right) // 核心动作
|
||
|
||
if node.left != nil: push(queue, node.left)
|
||
if node.right != nil: push(queue, node.right)
|
||
|
||
return root
|
||
```
|
||
|
||
### 方法三：深度优先搜索 DFS（迭代）⭐
|
||
|
||
除了 BFS 逐层翻转，DFS 也可以用显式栈来模拟递归过程。
|
||
|
||
> [!comparison] ⚖️ 三种写法对比
|
||
> | 维度 | DFS 递归 | BFS 迭代 | DFS 迭代 |
|
||
> |------|---------|---------|---------|
|
||
> | 代码简洁度 | ⭐⭐⭐ 仅需 4 行 | ⭐⭐ 需维护队列 | ⭐⭐ 需维护栈 |
|
||
> | 空间复杂度 | O(h) 递归栈 | O(w) 队列最大宽度 | O(h) 栈深度 |
|
||
> | 遍历顺序 | 前序（根→左→右） | 逐层（自顶向下） | 前序（自定义） |
|
||
> | 面试推荐度 | **首选** | 直观易懂 | 展示底层理解 |
|
||
|
||
> [!tip] 🔑 为什么 DFS 递归天然使用前序？
|
||
> 因为我们在深入子树**之前**就先做了交换动作（visit node first），所以是前序遍历的顺序。事实上，翻转可以在任何遍历时机进行——前序、中序、后序都可以完成翻转，最终结果是一样的。前序是最直观的：当前节点都交换完了再去孩子那里。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### DFS 递归伪代码
|
||
|
||
```
|
||
func invertTree(node):
|
||
if node == nil: return nil
|
||
|
||
// 递归翻转右子树和左子树，然后交换赋值
|
||
node.Left, node.Right = invertTree(node.Right), invertTree(node.Left)
|
||
|
||
return node
|
||
```
|
||
|
||
### BFS 迭代伪代码
|
||
|
||
```
|
||
if root == nil: return nil
|
||
|
||
queue = [root]
|
||
|
||
while len(queue) > 0:
|
||
node = pop(queue)
|
||
swap(node.left, node.right)
|
||
|
||
if node.left != nil: push(queue, node.left)
|
||
if node.right != nil: push(queue, node.right)
|
||
|
||
return root
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 翻转的遍历时机不影响结果
|
||
> 无论是前序、中序还是后序遍历，只要在每个节点上执行 swap(left, right)，最终翻转的结果都是一样的。这是因为翻转只关注"每个孩子节点都会被访问且交换一次"，与访问顺序无关。
|
||
>
|
||
> 但中序遍历需要小心！如果在交换后再走右边，原本的右子树现在已经变成了左子树，容易漏掉或重复处理。实际写起来比前/后序复杂。
|
||
|
||
> [!tip] 🔑 Go 多值赋值是杀手锏
|
||
> `node.Left, node.Right = node.Right, node.Left` 这一行同时完成了交换和简洁表达，是 Go 语言实现翻转的经典范式。
|
||
|
||
> [!info] 📊 复杂度速查
|
||
> | 方法 | 时间复杂度 | 空间复杂度 |
|
||
> |------|-----------|-----------|
|
||
> | DFS 递归 | **O(n)** — 每个节点访问一次 | **O(h)** — h 为树高，最坏 O(n)（链状），平均 O(log n)（平衡树） |
|
||
> | BFS 迭代 | **O(n)** — 每个节点入队出队各一次 | **O(w)** — w 为树的最大宽度，满二叉树最后一层最多 (n+1)/2 个节点 |
|
||
> | DFS 迭代 | **O(n)** | **O(h)** |
|
||
|
||
> [!note] 🧩 延伸思考
|
||
> - **对称二叉树**（LeetCode 101）：判断一棵树是否是它自己的镜像。思路和翻转高度相关——如果一棵树翻转后等于自身，它就是对称的。
|
||
> - **最小/最大深度**（LeetCode 104/111）：同样是经典的二叉树基础题，可对比练习。
|
||
> - **N 叉树翻转**：思路完全一致，只是把孩子切片反转而非交换两个指针。
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### DFS 递归法（推荐）⭐⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
func invertTree(root *TreeNode) *TreeNode {
|
||
// 终止条件：空节点不需要翻转
|
||
if root == nil {
|
||
return nil
|
||
}
|
||
|
||
// Go 多值赋值：右侧先全部求值，再同时赋给左侧
|
||
// 等价于：先把右子树翻转后变成新左孩子，左子树翻转后变成新右孩子
|
||
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
|
||
|
||
return root
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 226 题，通过率约 95%（Easy 中最高的题目之一）。代码仅 4 行核心逻辑，完美展示了递归的威力：**定义函数语义 → 假设子问题已解决 → 只需处理当前层**。
|
||
|
||
### BFS 层序遍历法（参考）⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
func invertTree(root *TreeNode) *TreeNode {
|
||
if root == nil {
|
||
return nil
|
||
}
|
||
|
||
var queue []*TreeNode // 使用切片模拟队列
|
||
queue = append(queue, root)
|
||
|
||
for len(queue) > 0 {
|
||
node := queue[0] // 出队
|
||
queue = queue[1:]
|
||
|
||
// 交换左右子节点
|
||
node.Left, node.Right = node.Right, node.Left
|
||
|
||
if node.Left != nil {
|
||
queue = append(queue, node.Left)
|
||
}
|
||
if node.Right != nil {
|
||
queue = append(queue, node.Right)
|
||
}
|
||
}
|
||
|
||
return root
|
||
}
|
||
```
|
||
|
||
> [!note] 🐹 Go 切片队列注意事项
|
||
> 上述 BFS 中使用 `queue = queue[1:]` 出队，随着循环进行切片头部不断缩小，底层数组无法释放。虽然在本题数据范围（≤ 100 节点）下毫无压力，但如果节点数量很大，建议使用双索引方式避免内存泄漏：
|
||
>
|
||
> ```go
|
||
> head := 0
|
||
> for head < len(queue) {
|
||
> node := queue[head]
|
||
> head++
|
||
> // ... 处理后追加新元素，queue 只会增长不会缩容
|
||
> }
|
||
> ```
|