树算法

一句话说明

树题本质上是在一棵分层结构里回答三件事：怎么遍历、怎么利用有序性质、怎么把子树答案合并起来。

先判断题目在问什么

flowchart TD
    A["树题"] --> B{"核心问题是什么?"}
    B -- "访问所有节点 / 输出顺序" --> C["遍历"]
    B -- "查找、插入、删除、有序性" --> D["BST"]
    B -- "路径、祖先、子树信息合并" --> E["递归 / 分治 / 树形 DP"]
    B -- "区间统计或动态前缀" --> F["线段树 / 树状数组"]
    B -- "字符串前缀匹配" --> G["Trie"]

最常用的选择表

树和图有什么区别

复习时很容易混淆

树可以看成一种特殊的图，但它没有环，而且大多数题都会给你一个明确的根。正因为“没有环 + 有根”，递归才会在树题里这么自然。

flowchart LR
    A["图题思维"] --> B["visited 防环"]
    C["树题思维"] --> D["递归定义子问题"]
    C --> E["前中后序决定处理时机"]

📚 核心主题

1. 二叉树遍历

• 前序遍历：根 -> 左 -> 右，适合“先处理当前节点”
• 中序遍历：左 -> 根 -> 右，BST 中最关键
• 后序遍历：左 -> 右 -> 根，适合“子树先算完”
• 层序遍历：按层 BFS，适合最小深度、右视图、层统计

2. 二叉树基本操作

• 树的高度
• 树的节点数
• 平衡二叉树
• 对称二叉树
• 翻转二叉树
• 合并二叉树

3. 二叉搜索树（BST）

• 验证 BST
• BST 查找
• BST 插入
• BST 删除
• BST 第 K 小

4. 经典树题

• 最近公共祖先
• 最大路径和
• 前序中序构造树
• 树的序列化
• 树形 DP：打家劫舍 III

5. 高级树结构

• Trie 树
• 线段树
• 树状数组
• 并查集

🧠 树题最常见的三种递归问法

一张图看前中后序

flowchart TD
    A["进入节点 root"] --> B["前序位置：先处理 root"]
    B --> C["递归左子树"]
    C --> D["中序位置：左边处理完后处理 root"]
    D --> E["递归右子树"]
    E --> F["后序位置：左右都处理完后处理 root"]

这个“处理时机”比“顺序名字”更重要

很多树题并不是让你真的输出遍历序列，而是让你把逻辑放在前序、中序或后序位置上。

建议学习顺序

1. 先掌握 前序、中序、后序、层序。
2. 再做 树高、平衡树 这类后序题。
3. 然后系统做 验证 BST、查找、删除。
4. 最后补 LCA、最大路径和、树形 DP。

易错点

树题里最常见的错误，是把“遍历顺序”和“递归时机”混为一谈。

• 前序 / 中序 / 后序，决定的是“当前节点什么时候处理”。
• 不是所有树题都要返回整棵树，很多题只需要子树返回一个值。
• 遇到 BST 时，要优先想到它的有序性质，不要按普通树处理。
• 如果题目问路径，先确认答案是“收集路径”还是“汇总子树信息”。

相关主题

• 图算法：树可以看成特殊图，但写法更偏递归
• 动态规划：树形 DP 属于状态设计的一种特殊形式
• 回溯算法：前序递归经常和路径搜索结合

---

返回：算法学习导航