树题型：解题思路与方法
树是面试中最依赖递归思维的题型。一旦理解了”当前节点 + 左右子树”这个模式，大部分树题都是改最后一行。
树的表示
数组表示
题目通常用 leftChild[i] 和 rightChild[i] 两个数组表示树，-1 表示没有子节点。
values = [4, 2, 6, 1, 3, 5, 7]
leftChild = [1, 3, 5, -1, -1, -1, -1]
rightChild = [2, 4, 6, -1, -1, -1, -1]
4(idx0)
/ \
2(idx1) 6(idx2)
/ \ / \
1(3) 3(4) 5(5) 7(6)
对象表示
LeetCode 上的标准定义：
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
}递归模板
所有树递归题的骨架：
function solve(node: TreeNode | null): 返回值 {
if (node === null) return 基线返回值 // 空节点
const left = solve(node.left) // 递归左子树
const right = solve(node.right) // 递归右子树
return 合并(left, right, node.val) // 合并结果
}三步：基线 → 递归左右 → 合并。大部分树题只改”合并”这一步。
常见树题模式
| 题型 | 合并方式 | 公式 |
|---|---|---|
| 树的高度 | max + 1 | max(left, right) + 1 |
| 判断平衡树 | max + 1 + 检查差值 | abs(left - right) <= 1 |
| 树的直径 | left + right | max(全局最大, left + right) |
| 翻转树 | 交换左右 | node.left = right; node.right = left |
| 最大深度 | max + 1 | max(left, right) + 1（和高度一样） |
| 最小深度 | min + 1 | min(left, right) + 1（注意空节点处理） |
| 相同的树 | 逻辑与 | left相同 && right相同 && 当前值相等 |
| 对称树 | 交叉比较 | 左左 == 右右 && 左右 == 右左 |
| 路径和 | 减法 | targetSum - node.val，叶子时检查是否为 0 |
识别信号
题目出现这些词，往树想：
- “二叉树/二叉搜索树/BST”
- “根节点/叶子节点/子树”
- “深度/高度/层数”
- “路径/路径和”
- “前序/中序/后序遍历”
- “层序/层次遍历”（BFS）
- “平衡/对称/相同”
三种遍历
遍历顺序的区别在于”当前节点”在什么时候处理：
1
/ \
2 3
前序：1 2 3（根左右，先处理自己再递归）
中序：2 1 3（左根右，BST 中序遍历得到有序序列）
后序：3 2 1（左右根，先递归再处理自己）
// 前序
function preorder(node) {
if (!node) return
process(node) // 先处理自己
preorder(node.left)
preorder(node.right)
}
// 中序
function inorder(node) {
if (!node) return
inorder(node.left)
process(node) // 中间处理自己
inorder(node.right)
}
// 后序
function postorder(node) {
if (!node) return
postorder(node.left)
postorder(node.right)
process(node) // 最后处理自己
}什么时候用哪种
| 遍历 | 适用场景 |
|---|---|
| 前序 | 先复制/创建节点、求深度、序列化 |
| 中序 | BST 有序输出、验证 BST、中序线索化 |
| 后序 | 释放节点、自底向上计算（如树高、直径） |
BFS 层序遍历
用队列，一层一层处理：
const queue: TreeNode[] = [root]
while (queue.length > 0) {
const node = queue.shift()!
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}适用场景：最短路径、按层处理、锯齿形遍历。
递归 vs 迭代
树题首选递归，代码最简洁。但有些场景需要迭代：
| 场景 | 选哪个 |
|---|---|
| 求高度/深度/直径 | 递归（后序） |
| 判断平衡/对称/相同 | 递归 |
| 层序遍历 | 迭代（BFS + 队列） |
| 前/中/后序遍历 | 递归或迭代（栈模拟递归） |
| 节点数很大 | 迭代（避免递归栈溢出） |
常见坑
- 空节点处理：
node === null必须先判，不然node.left报错。 - 最小深度陷阱：最小深度不能用
min(left, right) + 1，如果左子为空右子不为空，应该走右子。要单独处理只有单边子树的情况。 - BST 性质：左子值 < 父节点值 < 右子值。中序遍历 BST 得到的是升序序列。验证 BST 时不能只比较父子，要用上下界。
- 后序 vs 前序搞混：树的高度用后序（先算子树再算自己），序列化用前序（先处理自己再递归）。
- 迭代遍历栈模拟：前序迭代简单（先 push 右再 push 左），中序迭代需要一路向左压栈再弹出。
解题流程速查卡
1. 读题 → 识别"根/叶子/子树/深度/路径"
2. 确认树是数组表示还是对象表示
3. 写递归骨架：基线（null）→ 递归左右 → 合并
4. 问"当前节点需要做什么？" → 确定合并方式
5. 边界：空树、单节点、只有左子、只有右子
已做过的树题
- 22. Height of Binary Search Tree — 树的高度，递归基础模板