树
共 48 条分类条目，8 个题型小节； 每行标注难度、题号、原笔记摘要和 LeetCode 链接。
1. 树的遍历（基础）
9 条类型特点：树的遍历是所有树问题的基础，包括前序、中序、后序（DFS）和层序（BFS）。掌握递归和迭代两种写法是必须的。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 简单 | 144. 二叉树的前序遍历#144 LeetCode ↗ | 根左右，递归/迭代（栈） |
| 简单 | 94. 二叉树的中序遍历#94 LeetCode ↗ | 左根右，递归/迭代（栈） |
| 简单 | 145. 二叉树的后序遍历#145 LeetCode ↗ | 左右根，递归/迭代（栈） |
| 中等 | 102. 二叉树的层序遍历#102 LeetCode ↗ | 队列实现 BFS，按层输出 |
| 中等 | 107. 二叉树的层序遍历 II#107 LeetCode ↗ | 层序遍历后反转结果 |
| 中等 | 103. 二叉树的锯齿形层序遍历#103 LeetCode ↗ | 层序遍历 + 奇偶层方向标记 |
| 简单 | 589. N 叉树的前序遍历#589 LeetCode ↗ | N 叉树的 DFS 遍历 |
| 简单 | 590. N 叉树的后序遍历#590 LeetCode ↗ | N 叉树的 DFS 遍历 |
| 中等 | 429. N 叉树的层序遍历#429 LeetCode ↗ | N 叉树的 BFS 遍历 |
- 简单#144
根左右，递归/迭代（栈）
- 简单#94
左根右，递归/迭代（栈）
- 简单#145
左右根，递归/迭代（栈）
- 中等#102
队列实现 BFS，按层输出
- 中等#107
层序遍历后反转结果
- 中等#103
层序遍历 + 奇偶层方向标记
- 简单#589
N 叉树的 DFS 遍历
- 简单#590
N 叉树的 DFS 遍历
- 中等#429
N 叉树的 BFS 遍历
2. 树的性质与属性
8 条类型特点：这类题目考察树的深度、对称性、平衡性、直径等基本属性，通常用递归解决。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 简单 | 104. 二叉树的最大深度#104 LeetCode ↗ | 递归：max(左子树深度,右子树深度)+1 |
| 简单 | 111. 二叉树的最小深度#111 LeetCode ↗ | 注意叶子节点定义，递归需考虑单子树情况 |
| 简单 | 100. 相同的树#100 LeetCode ↗ | 同时递归比较两树节点 |
| 简单 | 101. 对称二叉树#101 LeetCode ↗ | 递归比较左子树的左和右子树的右 |
| 简单 | 110. 平衡二叉树#110 LeetCode ↗ | 递归计算高度，同时判断平衡性 |
| 简单 | LeetCode ↗ | 递归交换左右子树 |
| 简单 | 543. 二叉树的直径#543 LeetCode ↗ | 递归计算深度，直径 = 左深度 + 右深度 |
| 中等 | 662. 二叉树最大宽度#662 LeetCode ↗ | BFS 层序遍历，对节点编号 |
- 简单#104
递归：max(左子树深度,右子树深度)+1
- 简单#111
注意叶子节点定义，递归需考虑单子树情况
- 简单#100
同时递归比较两树节点
- 简单#101
递归比较左子树的左和右子树的右
- 简单#110
递归计算高度，同时判断平衡性
- 简单#226站内精讲
递归交换左右子树
- 简单#543
递归计算深度，直径 = 左深度 + 右深度
- 中等#662
BFS 层序遍历，对节点编号
3. 二叉搜索树（BST）
6 条类型特点：二叉搜索树的中序遍历是有序序列，利用这一特性可以解决验证 BST、第 K 小元素、转换 BST 等问题。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | 98. 验证二叉搜索树#98 LeetCode ↗ | 中序遍历检查是否递增，或递归传递上下界 |
| 简单 | 700. 二叉搜索树中的搜索#700 LeetCode ↗ | 利用 BST 性质，递归或迭代查找 |
| 简单 | LeetCode ↗ | 递归取中间节点作为根 |
| 中等 | LeetCode ↗ | 中序遍历计数，或记录子树节点数 |
| 中等 | LeetCode ↗ | 利用大小关系：p,q 分居两侧则当前节点为 LCA |
| 中等 | LeetCode ↗ | 反序中序遍历（右-根-左），累加节点值 |
- 中等#98
中序遍历检查是否递增，或递归传递上下界
- 简单#700
利用 BST 性质，递归或迭代查找
- 简单#108
递归取中间节点作为根
- 中等#230
中序遍历计数，或记录子树节点数
- 中等#235
利用大小关系：p,q 分居两侧则当前节点为 LCA
- 中等#538
反序中序遍历（右-根-左），累加节点值
4. 树的路径与求和
6 条类型特点：这类题目要求计算从根到叶子或任意节点之间的路径和，通常用 DFS 回溯解决。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 简单 | 112. 路径总和#112 LeetCode ↗ | DFS 递减 target，判断叶子节点时是否归零 |
| 中等 | 113. 路径总和 II#113 LeetCode ↗ | DFS + 回溯，记录所有满足条件的路径 |
| 中等 | 437. 路径总和 III#437 LeetCode ↗ | 前缀和 + 哈希表优化（树上的两数之和） |
| 简单 | 257. 二叉树的所有路径#257 LeetCode ↗ | DFS 回溯，记录路径字符串 |
| 中等 | LeetCode ↗ | DFS 累加路径数字 |
| 困难 | 124. 二叉树中的最大路径和#124 LeetCode ↗ | 递归计算单侧贡献，全局变量记录最大值 |
- 简单#112
DFS 递减 target，判断叶子节点时是否归零
- 中等#113
DFS + 回溯，记录所有满足条件的路径
- 中等#437
前缀和 + 哈希表优化（树上的两数之和）
- 简单#257
DFS 回溯，记录路径字符串
- 中等#129
DFS 累加路径数字
- 困难#124
递归计算单侧贡献，全局变量记录最大值
5. 树的构造与序列化
5 条类型特点：给定两种遍历序列（如前序+中序）重建二叉树，或者将树序列化为字符串再反序列化。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | LeetCode ↗ | 前序确定根，中序分割左右子树，递归构建 |
| 中等 | LeetCode ↗ | 后序确定根，中序分割左右子树 |
| 中等 | 654. 最大二叉树#654 LeetCode ↗ | 递归找最大值作为根 |
| 中等 | LeetCode ↗ | 前序遍历 + 特殊标记空节点 |
| 中等 | LeetCode ↗ | 利用 BST 性质优化序列化 |
- 中等#105
前序确定根，中序分割左右子树，递归构建
- 中等#106
后序确定根，中序分割左右子树
- 中等#654
递归找最大值作为根
- 中等#297
前序遍历 + 特殊标记空节点
- 中等#449
利用 BST 性质优化序列化
6. 最近公共祖先（LCA）
3 条类型特点：寻找两个节点的最近公共祖先，是树中非常重要的算法，也是面试高频题。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | 236. 二叉树的最近公共祖先#236 LeetCode ↗ | 递归查找：如果左右子树分别找到 p,q 则当前节点为 LCA |
| 中等 | LeetCode ↗ | 利用大小关系快速判断 |
| 中等 | 1644. 二叉树的最近公共祖先 II#1644 LeetCode ↗ | 考虑节点可能不存在的情况 |
- 中等#236
递归查找：如果左右子树分别找到 p,q 则当前节点为 LCA
- 中等#235
利用大小关系快速判断
- 中等#1644
考虑节点可能不存在的情况
7. 层序遍历变种
5 条类型特点：在层序遍历的基础上，增加一些额外要求，如右视图、每层最大值、每层平均值等。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | 199. 二叉树的右视图#199 LeetCode ↗ | 层序遍历，记录每层最后一个节点 |
| 中等 | 637. 二叉树的层平均值#637 LeetCode ↗ | 层序遍历，计算每层平均值 |
| 中等 | 515. 在每个树行中找最大值#515 LeetCode ↗ | 层序遍历，记录每层最大值 |
| 中等 | 513. 找树左下角的值#513 LeetCode ↗ | BFS 从右往左遍历，最后一个节点即左下角 |
| 中等 | 1161. 最大层内元素和#1161 LeetCode ↗ | 层序遍历，计算每层和 |
- 中等#199
层序遍历，记录每层最后一个节点
- 中等#637
层序遍历，计算每层平均值
- 中等#515
层序遍历，记录每层最大值
- 中等#513
BFS 从右往左遍历，最后一个节点即左下角
- 中等#1161
层序遍历，计算每层和
8. 其他进阶问题
6 条类型特点：这类题目涉及更复杂的树结构（如 N 叉树、Trie 树）或更巧妙的算法思想。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | LeetCode ↗ | 利用已建立的 next 指针进行层序遍历 |
| 中等 | LeetCode ↗ | 非完美二叉树，同样可用 BFS 或利用 next |
| 中等 | 114. 二叉树展开为链表#114 LeetCode ↗ | 前序遍历展开，原地修改 |
| 中等 | LeetCode ↗ | 多叉树结构，每个节点存储子节点映射 |
| 困难 | 212. 单词搜索 II#212 LeetCode ↗ | Trie + 回溯 |
| 困难 | 968. 监控二叉树#968 LeetCode ↗ | 树形 DP，状态转移 |
- 中等#116
利用已建立的 next 指针进行层序遍历
- 中等#117
非完美二叉树，同样可用 BFS 或利用 next
- 中等#114
前序遍历展开，原地修改
- 中等#208
多叉树结构，每个节点存储子节点映射
- 困难#212
Trie + 回溯
- 困难#968
树形 DP，状态转移