320 lines
9.6 KiB
Markdown
320 lines
9.6 KiB
Markdown
---
|
||
tags: ["LeetCode", "二叉树", "深度优先搜索", "广度优先搜索", "递归", "简单"]
|
||
create time: 2026-05-17 10:30
|
||
---
|
||
|
||
# 37-二叉树的最大深度
|
||
|
||
## 题面
|
||
|
||
给定一个二叉树 `root`，返回其**最大深度**。
|
||
|
||
二叉树的 **最大深度** 是指从根节点到最远叶子节点的最长路径上的节点数。
|
||
|
||
> [!info] 💡 核心概念：什么是「深度」？
|
||
> - 根节点的深度为 **1**
|
||
> - 每往下一层，深度 **+1**
|
||
> - 「最大深度」= 从根到**最远叶子节点**经过的节点总数
|
||
>
|
||
> > [!question] 🤔 思考：深度和高度有什么区别？
|
||
> > - **深度（Depth）**：从根节点到当前节点的距离（自顶向下计数）
|
||
> > - **高度（Height）**：从当前节点到最远叶子节点的距离（自底向上计数）
|
||
> > - 根节点的高度 = 整棵树的最大深度，这是一个重要等价关系！
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：root = [3,9,20,null,null,15,7]
|
||
输出：3
|
||
解释：
|
||
3 深度为 1
|
||
/ \ ┌─────────────┐
|
||
9 20 │ 最长路径：3→20→15 或 3→20→7 │
|
||
│ 共 3 个节点，故深度为 3 │
|
||
/ \ └─────────────┘
|
||
15 7
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：root = [1,null,2]
|
||
输出：2
|
||
解释：树退化为链状 1→2，深度为 2
|
||
```
|
||
|
||
**约束：**
|
||
|
||
- 树中节点的数量在 `[0, 10^4]` 区间内
|
||
- `-100 <= Node.val <= 100`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
### 方法一：深度优先搜索 DFS（递归）⭐⭐
|
||
|
||
#### 核心洞察
|
||
|
||
> [!question] 💡 思考
|
||
> 对于任意一棵子树，它的最大深度等于什么？假设你已经知道左子树深度是 `L`、右子树深度是 `R`，那么这棵树的深度是多少？
|
||
|
||
答案一目了然：**`max(L, R) + 1`**。这个 `+1` 就是当前根节点自身。
|
||
|
||
这是典型的**自底向上**计算：先求出左右子树的答案，再合并得到当前结果。
|
||
|
||
#### 递归三要素
|
||
|
||
| 要素 | 内容 |
|
||
|------|------|
|
||
| **终止条件** | 节点为空时，深度为 0 |
|
||
| **递归表达式** | `depth(node) = max(depth(node.left), depth(node.right)) + 1` |
|
||
| **返回值** | 以 `node` 为根的树的深度 |
|
||
|
||
#### 执行流程图
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["maxDepth(3)"] --> B["maxDepth(9)"]
|
||
B --> C["maxDepth(nil) → 0"]
|
||
B --> D["maxDepth(nil) → 0"]
|
||
B --> E["max(0,0)+1 = 1 ✅"]
|
||
A --> F["maxDepth(20)"]
|
||
F --> G["maxDepth(15)"]
|
||
G --> H["maxDepth(nil) → 0"]
|
||
G --> I["maxDepth(nil) → 0"]
|
||
G --> J["max(0,0)+1 = 1 ✅"]
|
||
F --> K["maxDepth(7)"]
|
||
K --> L["maxDepth(nil) → 0"]
|
||
K --> M["maxDepth(nil) → 0"]
|
||
K --> N["max(0,0)+1 = 1 ✅"]
|
||
F --> O["max(1,1)+1 = 2 ✅"]
|
||
A --> P["max(1,2)+1 = 3 ✅"]
|
||
|
||
style E fill:#d4edda
|
||
style N fill:#d4edgreen
|
||
style O fill:#cce5ff
|
||
style P fill:#f8d7da,stroke:#721c24
|
||
```
|
||
|
||
> [!note] 🧠 递归的执行视角
|
||
> 想象一下：每个调用帧都在等待子调用的返回值，就像每个人都在等下属报业绩后再决定自己的绩效。直到遇到空节点（叶子之下），返回值逐层冒泡上来，层层累加 `+1`，最终算出整棵树的深度。
|
||
|
||
#### 为什么正确？
|
||
|
||
利用数学归纳法可以证明：
|
||
|
||
- **基准情况**：空树深度为 0 ✅
|
||
- **归纳步骤**：假设所有高度小于 `h` 的子树都能正确返回深度，那么高度为 `h` 的树取其左右子树深度的最大值再加 1，显然也正确 ✅
|
||
|
||
### 方法二：广度优先搜索 BFS（层序遍历）⭐
|
||
|
||
除了「自底向上」的递归思路，还可以「自顶向下」逐层扫描——这正是 BFS 的拿手好戏。
|
||
|
||
#### 核心思想
|
||
|
||
BFS 天然按层访问节点。**遍历了多少层，树的深度就是多少。**
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["层1: [3]"] -->|"深度 = 1"| B["层2: [9, 20]"]
|
||
B -->|"深度 = 2"| C["层3: [15, 7]"]
|
||
C -->|"深度 = 3"| D["无更多层\n返回 3 ✅"]
|
||
|
||
style A fill:#e8f5e9
|
||
style B fill:#fff3e0
|
||
style C fill:#e3f2fd
|
||
style D fill:#fce4ec
|
||
```
|
||
|
||
#### 算法骨架
|
||
|
||
```
|
||
初始化队列 queue，放入 root
|
||
depth = 0
|
||
|
||
while queue 非空:
|
||
depth++ // 又扫完了一层
|
||
n = queue.length // 固定当前层的节点数
|
||
|
||
for i from 0 to n-1: // 只处理当前层的节点
|
||
node = queue.pop()
|
||
if node.left != nil:
|
||
push queue, node.left
|
||
if node.right != nil:
|
||
push queue, node.right
|
||
|
||
return depth
|
||
```
|
||
|
||
> [!warning] ⚠️ 关键细节
|
||
> 每一层开始前必须先记录 `n = queue.length`！如果直接在 `for` 循环里判断 `len(queue) > 0`，会因为子节点不断入队而导致死循环。
|
||
|
||
#### DFS vs BFS 如何选择？
|
||
|
||
> [!comparison] ⚖️ 深度优先 vs 广度优先
|
||
> | 维度 | DFS（递归） | BFS（层序遍历） |
|
||
> |------|------------|----------------|
|
||
> | 代码简洁度 | ⭐⭐⭐ 仅需 3 行核心逻辑 | ⭐⭐ 需维护队列和层计数器 |
|
||
> | 空间复杂度 | O(h)，递归栈深度 | O(w)，队列最多存一层宽度 |
|
||
> | 实际效率 | 递归有函数调用开销 | 迭代，无调用开销 |
|
||
> | 适用场景 | 通用解法，面试首选 | 需要按层处理问题时自然得出 |
|
||
|
||
> [!tip] 🔑 何时选哪种？
|
||
> - 如果只问最大深度：**DFS 更简洁**，直接 return max(left, right) + 1
|
||
> - 如果问「每层最大值」「锯齿形遍历」等按层相关的问题：**BFS 天然适合**
|
||
> - 面试中两者都可以，DFS 通常更高效因为不需要额外维护队列结构
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### DFS 伪代码
|
||
|
||
```
|
||
func maxDepth(node):
|
||
if node == nil:
|
||
return 0
|
||
|
||
left = maxDepth(node.left) // 左子树深度
|
||
right = maxDepth(node.right) // 右子树深度
|
||
|
||
return max(left, right) + 1 // 取较大者 + 当前节点
|
||
```
|
||
|
||
### BFS 伪代码
|
||
|
||
```
|
||
if root == nil: return 0
|
||
|
||
queue = [root]
|
||
depth = 0
|
||
|
||
while len(queue) > 0:
|
||
depth++
|
||
n = len(queue)
|
||
|
||
for i from 0 to n-1: // 只处理当前层的节点
|
||
node = pop queue
|
||
if node.left != nil:
|
||
push queue, node.left
|
||
if node.right != nil:
|
||
push queue, node.right
|
||
|
||
return depth
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 最大深度 = 最大高度（根节点视角）
|
||
> 这道题本质上求的是「根节点的高度」。反过来想，**最小深度**则是「根到最近叶子节点」的距离。注意最小深度要求叶子节点（左右子树都为空），不能把有一侧子树为空的情况也算作叶子。
|
||
|
||
> [!tip] 🔑 一句代码搞定（Go 语言）
|
||
> ```go
|
||
> func maxDepth(root *TreeNode) int {
|
||
> if root == nil { return 0 }
|
||
> return imax(maxDepth(root.Left), maxDepth(root.Right)) + 1
|
||
> }
|
||
> ```
|
||
> Go 标准库没有 `max` 泛函数（截至 1.21），需要自己写一个辅助函数或用 `if` 判断。Go 1.21+ 的 `slices.Max` 仅适用于切片，不适用于两个标量比较。
|
||
|
||
> [!note] 📊 复杂度速查
|
||
> | 方法 | 时间复杂度 | 空间复杂度 |
|
||
> |------|-----------|-----------|
|
||
> | DFS 递归 | **O(n)** — 每个节点访问一次 | **O(h)** — h 为树高，最坏 O(n)（链状），平均 O(log n)（平衡树） |
|
||
> | BFS 迭代 | **O(n)** — 每个节点入队出队各一次 | **O(w)** — w 为树的最大宽度，最坏 O(n)（满二叉树最后一层） |
|
||
|
||
> [!info] 🧩 延伸思考
|
||
> 如果把「最大深度」改成「直径」（任意两节点间的最长路径），思路会如何变化？答案是在每个节点同时记录「深度」和「经过该节点的最长路径」，用全局变量实时更新最大值。见 LeetCode 543. 二叉树的直径。
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### DFS 递归法（推荐）⭐⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
func maxDepth(root *TreeNode) int {
|
||
// 终止条件：空节点的深度为 0
|
||
if root == nil {
|
||
return 0
|
||
}
|
||
|
||
// 递归求左右子树的深度
|
||
left := maxDepth(root.Left) // 左子树深度
|
||
right := maxDepth(root.Right) // 右子树深度
|
||
|
||
// 当前节点深度 = 较深子树 + 1
|
||
if left > right {
|
||
return left + 1
|
||
}
|
||
return right + 1
|
||
}
|
||
|
||
// 辅助函数：求两个整数的较大值
|
||
// Go 1.21 以下没有内置 max(int, int)，需自行实现
|
||
func max(a, b int) int {
|
||
if a > b {
|
||
return a
|
||
}
|
||
return b
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 104 题，通过率约 73%。作为二叉树入门第一题，它完美展示了递归的「分而治之」思想：**将大问题拆解为相同形式的子问题**，直到触及最简单的边界（空节点）。
|
||
|
||
### BFS 层序遍历法（参考）⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
func maxDepth(root *TreeNode) int {
|
||
if root == nil {
|
||
return 0
|
||
}
|
||
|
||
var queue []*TreeNode // 使用切片模拟队列
|
||
queue = append(queue, root)
|
||
depth := 0
|
||
|
||
for len(queue) > 0 {
|
||
n := len(queue) // 固定当前层的节点数量
|
||
depth++ // 遍历了一层，深度 +1
|
||
|
||
for i := 0; i < n; i++ {
|
||
node := queue[0] // 出队
|
||
queue = queue[1:] // 切片弹出首部
|
||
|
||
if node.Left != nil {
|
||
queue = append(queue, node.Left) // 左孩子入队
|
||
}
|
||
if node.Right != nil {
|
||
queue = append(queue, node.Right) // 右孩子入队
|
||
}
|
||
}
|
||
}
|
||
|
||
return depth
|
||
}
|
||
```
|
||
|
||
> [!note] 🐹 Go 队列优化提示
|
||
> 上述 BFS 使用 `queue = queue[1:]` 出队，但切片头部不断删除会导致底层数组无法释放，内存只增不减。在实际工程中可以用双指针（head/tail 索引）避免缩容；但在这道题的数据范围（≤ 10^4 节点）下，两种写法差异可忽略，教学场景以最清晰为准。
|