421 lines
13 KiB
Markdown
421 lines
13 KiB
Markdown
---
|
||
tags: ["LeetCode", "二叉树", "深度优先搜索", "递归", "后序遍历"]
|
||
create time: 2026-05-17 12:00
|
||
---
|
||
|
||
# 40-二叉树的直径
|
||
|
||
## 题面
|
||
|
||
给你一棵二叉树的根节点，返回该树的 **直径**。
|
||
|
||
> [!question] 💡 核心定义
|
||
> - **直径** = 树中任意两个节点之间最长路径的 **边数**
|
||
> - 这条路径可能经过也可能 **不经过** 根节点
|
||
> - 「长度」= 路径上的 **边数**（不是节点数！）
|
||
|
||
> [!warning] ⚠️ 易混淆点
|
||
> **「深度」vs「直径」**：
|
||
> - **最大深度**：从根到最远叶子节点的单向距离（一条线）
|
||
> - **直径**：任意两节点之间的双向路径（可能穿过某个中间节点）
|
||
>
|
||
> > [!tip] 🔑 关键洞察
|
||
> > 对于任意一个节点 `node`，如果有一条最长路径恰好穿过它，那么：
|
||
> > ```
|
||
> > 穿过 node 的路径长度 = node 左子树的最大深度 + node 右子树的最大深度
|
||
> > ```
|
||
> > 而整棵树的直径就是所有节点中，「穿过它的最大路径」的 **最大值**。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：root = [1,2,3,4,5]
|
||
输出：3
|
||
解释：取路径 [4→2→1→3] 或 [5→2→1→3]，共 3 条边。
|
||
|
||
1 ← 直径穿过了 1
|
||
/ \
|
||
2 3 ← 路径可以是 4→2→1→3
|
||
/ \
|
||
4 5
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：root = [1,2]
|
||
输出：1
|
||
解释：只有 1→2 这一条边
|
||
```
|
||
|
||
**约束：**
|
||
|
||
- 树中节点数目在范围 `[1, 10^4]` 内
|
||
- `-100 <= Node.val <= 100`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
### 方法一：DFS 后序遍历 + 全局最大值 ⭐⭐⭐
|
||
|
||
#### 核心洞察
|
||
|
||
> [!question] 🤔 思考
|
||
>
|
||
> 第 37 题我们求过「最大深度」——它是从根出发往下走的最远距离。
|
||
> 现在要求「直径」——它可以是树上**任意两节点**之间的距离。
|
||
>
|
||
> 想象你在树上找最长路径，它会「穿过」某个节点：从上侧一棵子树上来，再从下侧另一棵子树下去。**这个「中间节点」不一定是根！**
|
||
|
||
以 `[] (1,2,3,4,5)` 为例，逐步计算每个节点的数据：
|
||
|
||
```
|
||
1 ← 左深=2, 右深=1, 穿过它的直径=3 ✅ 答案!
|
||
/ \
|
||
2 3 ← 节点3是叶子：左深=0, 右深=0, 直径贡献=0
|
||
/ \
|
||
4 5 ← 节点4,5都是叶子：深度各为0, 直径贡献各为0
|
||
```
|
||
|
||
> [!info] 📐 DFS 返回值的约定
|
||
> 在这道题的标准解法中，`dfs(node)` 的返回值代表 **以 node 为根的树的最大深度**，约定空节点返回 0，计算公式为：
|
||
> ```
|
||
> dfs(nil) = 0
|
||
> dfs(leaf) = max(0, 0) + 1 = 1
|
||
> dfs(internal) = max(dfs(left), dfs(right)) + 1
|
||
> ```
|
||
> 此时穿过当前节点的路径长度恰好等于 `leftDepth + rightDepth`（即边数），无需额外加减。验证：节点 1 的左深度 = 2、右深度 = 1，穿过它的路径 = 2+1 = 3 条边 ✅
|
||
|
||
执行流程图解：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
Post["后序遍历：先子节点，后自身"] --> L["遍历左子树，获得左深度"]
|
||
L --> R["遍历右子树，获得右深度"]
|
||
R --> C["当前节点处更新直径\n通过此节点的路径 = 左深度 + 右深度"]
|
||
C --> Ret["返回当前节点的最大深度\n给父节点使用"]
|
||
|
||
style Post fill:#fff3e0,stroke:#e65100
|
||
style C fill:#fce4ec,stroke:#c62828
|
||
style Ret fill:#e3f2fd,stroke:#1565c0
|
||
|
||
linkStyle 0,1,2 stroke-width:3px
|
||
```
|
||
|
||
具体对 `[] (1,2,3,4,5)` 每个节点的详细计算：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
N4["节点 4\n左深=0, 右深=0\n直径贡献=0\n返回 max=0"]
|
||
N5["节点 5\n左深=0, 右深=0\n直径贡献=0\n返回 max=0"]
|
||
N3["节点 3\n左深=0, 右深=0\n直径贡献=0\n返回 max=0"]
|
||
N2["节点 2\n左深=1, 右深=1\n直径贡献=1+1=2, ans=2\n返回 max=1"]
|
||
N1["节点 1\n左深=2, 右深=1\n直径贡献=2+1=3, ans=3\n返回 max=2"]
|
||
|
||
N4 & N5 --> N2
|
||
N3 --> N1
|
||
N2 --> N1
|
||
|
||
style N4 fill:#e3f2fd
|
||
style N5 fill:#e3f2fd
|
||
style N3 fill:#e3f2fd
|
||
style N2 fill:#fff3e0,stroke:#e65100
|
||
style N1 fill:#fce4ec,stroke:#c62828,stroke-width:3px
|
||
```
|
||
|
||
执行流程图解：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
Post["后序遍历：先子节点，后自身"] --> L["遍历左子树，获得左深度"]
|
||
L --> R["遍历右子树，获得右深度"]
|
||
R --> C["当前节点处更新直径\n通过此节点的路径 = 左深度 + 右深度"]
|
||
C --> Ret["返回当前节点的最大深度\n给父节点使用"]
|
||
|
||
style Post fill:#fff3e0,stroke:#e65100
|
||
style C fill:#fce4ec,stroke:#c62828
|
||
style Ret fill:#e3f2fd,stroke:#1565c0
|
||
|
||
linkStyle 0,1,2 stroke-width:3px
|
||
```
|
||
|
||
具体对 `[] (1,2,3,4,5)` 每个节点的详细计算：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
N4["节点 4\n左深=0, 右深=0\n直径贡献=0\n返回 max=0"]
|
||
N5["节点 5\n左深=0, 右深=0\n直径贡献=0\n返回 max=0"]
|
||
N3["节点 3\n左深=0, 右深=0\n直径贡献=0\n返回 max=0"]
|
||
N2["节点 2\n左深=max(4)=1, 右深=max(5)=1\n直径贡献=1+1=2, ans=2\n返回 max=1"]
|
||
N1["节点 1\n左深=max(2)=2, 右深=max(3)=1\n直径贡献=2+1=3, ans=3\n返回 max=2"]
|
||
|
||
N4 & N5 --> N2
|
||
N3 --> N1
|
||
N2 --> N1
|
||
|
||
style N4 fill:#e3f2fd
|
||
style N5 fill:#e3f2fd
|
||
style N3 fill:#e3f2fd
|
||
style N2 fill:#fff3e0,stroke:#e65100
|
||
style N1 fill:#fce4ec,stroke:#c62828,stroke-width:3px
|
||
```
|
||
|
||
#### 算法框架
|
||
|
||
```
|
||
global ans = 0
|
||
|
||
function dfs(node):
|
||
if node == nil:
|
||
return 0
|
||
|
||
// 后序：先左右子树，再当前节点
|
||
left = dfs(node.left) // 左子树的最大深度
|
||
right = dfs(node.right) // 右子树的最大深度
|
||
|
||
// 穿过当前节点的路径长度 = 左深度 + 右深度
|
||
ans = max(ans, left + right)
|
||
|
||
// 返回当前节点向上延伸的最大深度（供父节点使用）
|
||
return max(left, right) + 1
|
||
|
||
function diameterOfBinaryTree(root):
|
||
dfs(root)
|
||
return ans
|
||
```
|
||
|
||
#### 递归三要素
|
||
|
||
| 要素 | 内容 |
|
||
|------|------|
|
||
| **终止条件** | 节点为空时，返回 0 |
|
||
| **递归表达式** | `left = dfs(node.left)`, `right = dfs(node.right)` |
|
||
| **副作用** | 在每个节点更新全局变量 `ans = max(ans, left + right)` |
|
||
| **返回值** | 以当前节点为根的树的最大深度 `max(left, right) + 1` |
|
||
|
||
#### 为什么用后序遍历？
|
||
|
||
> [!info] 🧠 自底向上的必然选择
|
||
> 要计算「穿过节点 A 的直径」，必须先知道 A 的左右子树各自有多深。这意味着**子节点的处理必须在父节点之前完成**——正是后序遍历（左 → 右 → 根）的执行顺序。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### DFS 伪代码
|
||
|
||
```
|
||
// 全局变量：记录最大直径
|
||
ans = 0
|
||
|
||
func dfs(node):
|
||
if node == nil:
|
||
return 0
|
||
|
||
left = dfs(node.Left) // 左子树深度（边数视角下的"层数"）
|
||
right = dfs(node.Right) // 右子树深度
|
||
|
||
ans = max(ans, left + right) // 更新直径
|
||
|
||
return max(left, right) + 1 // 返回当前节点深度给父节点
|
||
|
||
func diameterOfBinaryTree(root):
|
||
dfs(root)
|
||
return ans
|
||
```
|
||
|
||
### Go 语言实现要点
|
||
|
||
> [!note] 🐹 Go 中没有真正的"全局变量"最佳实践
|
||
> 在这道题中，有几种方式传递和修改 `ans`：
|
||
|
||
| 方案 | 写法 | 推荐度 |
|
||
|------|------|--------|
|
||
| **指针传参** | `func dfs(node *TreeNode, ans *int)` | ⭐⭐⭐ 函数式风格，无副作用 |
|
||
| **闭包捕获** | 在 `diameterOfBinaryTree` 内定义 `var ans int` 然后用嵌套函数访问 | ⭐⭐⭐ 简洁直观 |
|
||
| **返回值携带** | `func dfs(...) (depth, dia int)` | ⭐⭐ 稍显繁琐 |
|
||
|
||
推荐使用 **闭包捕获** 的方式，既干净又自然。
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 直径 vs 深度的关系速记
|
||
> - **深度**：从某节点向下到最远叶子的「单向」路径长度
|
||
> - **直径**：从某节点向「左下 + 右下」延伸的两条分支合并后的总长
|
||
> - **公式**：`diameter(node) = leftDepth + rightDepth`
|
||
> - 整棵树的直径是所有节点中这个值的 **最大值**
|
||
|
||
> [!tip] 🔑 为什么可以用一次 DFS 搞定？
|
||
> 很多人第一反应是「枚举每对节点 → BFS/DFS 求距离 → 取最大值」，这样是 O(n²)。但其实：
|
||
> - 对于每个节点，穿过它的直径 = 左深度 + 右深度
|
||
> - 左深度和右深度可以通过一次后序遍历全部算出
|
||
> - 同时更新全局最大值，只需 **O(n)** 时间
|
||
|
||
> [!warning] ⚠️ 常见错误
|
||
> 1. **误把直径当作最大深度 × 2**：只有满二叉树/完美二叉树时才碰巧相等
|
||
> 2. **忘记处理单边树的情况**：比如左斜树，右深度恒为 0，直径 = 最大深度
|
||
> 3. **把直径当成经过根的路径**：直径可能经过任何节点，不只是根
|
||
|
||
> [!info] 📊 复杂度速查
|
||
> | 维度 | 结果 |
|
||
> |------|------|
|
||
> | 时间复杂度 | **O(n)** — 每个节点恰好访问一次 |
|
||
> | 空间复杂度 | **O(h)** — h 为树高，递归栈深度；最坏 O(n)（链状），平均 O(log n)（平衡树） |
|
||
|
||
> [!connection] 🔗 与相关题目的联系
|
||
> - **[37-二叉树的最大深度](./37-二叉树的最大深度.md)**：直径问题的基础，深度是计算直径的子组件
|
||
> - **[543. Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/)**：原题（英文）
|
||
> 两者本质相同，只是表述不同
|
||
> - **最长路径问题**：这是一般图论中「树的直径」的特例。对无权树可通过两次 BFS 求解，但二叉树场景下 DFS 更直接
|
||
|
||
> [!exercise] 💪 变体练习
|
||
> 1. 如果路径长度定义为节点数而非边数，如何修改代码？→ 只需将 `left + right` 改为 `left + right + 1`（当前节点也计入）
|
||
> 2. 如果树中有负权边（加权二叉树），还能用此方法吗？→ 不能，需要换成分治或树形 DP
|
||
> 3. N 叉树的直径如何求解？→ 取最大的两个子节点深度之和作为直径贡献
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### DFS + 闭包（推荐）⭐⭐⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
func diameterOfBinaryTree(root *TreeNode) int {
|
||
// ans 通过闭包捕获，DFS 过程中不断刷新最大值
|
||
ans := 0
|
||
|
||
// dfs 返回以 node 为根的树的最大深度（层数）
|
||
var dfs func(*TreeNode) int
|
||
dfs = func(node *TreeNode) int {
|
||
if node == nil {
|
||
return 0
|
||
}
|
||
|
||
// 后序遍历：先获取左右子树的深度
|
||
left := dfs(node.Left) // 左子树的最大深度
|
||
right := dfs(node.Right) // 右子树的最大深度
|
||
|
||
// 穿过当前节点的路径 = 左深度 + 右深度
|
||
// 这就是以当前节点为"最高点"的最长路径
|
||
dia := left + right
|
||
if dia > ans {
|
||
ans = dia
|
||
}
|
||
|
||
// 返回当前节点向上传递的最大深度
|
||
// 供父节点计算穿过它的直径时使用
|
||
if left > right {
|
||
return left + 1
|
||
}
|
||
return right + 1
|
||
}
|
||
|
||
dfs(root)
|
||
return ans
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 543 题，通过率约 62%。核心只有一句话：**在每个节点处，用左深度+右深度更新答案，同时返回 max(左,右)+1**。面试时可先用一句话概括思路，再展开细节。
|
||
|
||
### DFS + 指针传参（函数式风格）⭐⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
func diameterOfBinaryTree(root *TreeNode) int {
|
||
if root == nil {
|
||
return 0
|
||
}
|
||
|
||
maxDia := 0
|
||
|
||
// dfs 返回深度，通过指针修改 maxDia
|
||
var dfs func(*TreeNode) int
|
||
dfs = func(node *TreeNode) int {
|
||
if node == nil {
|
||
return 0
|
||
}
|
||
|
||
left := dfs(node.Left)
|
||
right := dfs(node.Right)
|
||
|
||
*maxDia = left + right
|
||
if d := left + right; d > *maxDia {
|
||
*maxDia = d
|
||
}
|
||
|
||
if left > right {
|
||
return left + 1
|
||
}
|
||
return right + 1
|
||
}
|
||
|
||
dfs(root)
|
||
return *maxDia
|
||
}
|
||
```
|
||
|
||
> [!note] 🐹 两种写法的选择
|
||
> 闭包方式中 `ans` 是外层函数的局部变量，内层 `dfs` 直接读取和赋值，无需额外类型声明。指针方式更"显式"地表明 `dfs` 会修改外部状态，在团队协作中可读性更强。个人偏好闭包——Go 的闭包在语法上是原生支持的，不需要像 Java/C++ 那样用 `AtomicInteger` 或引用包装类。
|
||
|
||
### 对比：错误思路（仅考虑经过根的直径）❌
|
||
|
||
```go
|
||
// ❌ 错误示范：这样做只能得到"经过根节点的直径"
|
||
func wrongApproach(root *TreeNode) int {
|
||
if root == nil {
|
||
return 0
|
||
}
|
||
// 只计算了穿过根节点的路径！
|
||
// 如果最长路径不经过根，就会返回错误结果
|
||
left := maxDepth(root.Left)
|
||
right := maxDepth(root.Right)
|
||
return left + right
|
||
}
|
||
|
||
func maxDepth(node *TreeNode) int {
|
||
if node == nil {
|
||
return 0
|
||
}
|
||
l, r := maxDepth(node.Left), maxDepth(node.Right)
|
||
if l > r {
|
||
return l + 1
|
||
}
|
||
return r + 1
|
||
}
|
||
```
|
||
|
||
> [!failure] ❌ 为什么不正确？
|
||
> 上面的代码只考虑了穿过根节点的直径，但对于 `[] (1,2,null,3,4)`：
|
||
>
|
||
> ```
|
||
> 1
|
||
> /
|
||
> 2
|
||
> / \
|
||
> 3 4
|
||
> ```
|
||
>
|
||
> 经过根的直径 = 1（左）+ 0（右）= 1
|
||
> 但正确答案是经过节点 2 的路径 3→2→4，长度为 **2**
|
||
>
|
||
> **必须用 DFS 在后序遍历过程中逐个节点尝试，才能覆盖所有可能！**
|