wonder/leetcode-go
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
leetcode-go/二叉树/37-二叉树的最大深度.md
T

320 lines
9.6 KiB
Markdown
Raw Permalink Normal View History

vault backup: 2026-05-17 14:27:46
2026-05-17 14:27:46 +08:00
---
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 节点）下，两种写法差异可忽略，教学场景以最清晰为准。
Reference in New Issue Copy Permalink