刷题范围
基础题目
98.验证二叉搜索树
扩展题目
700.二叉搜索树中的搜索
938.二叉搜索树的范围和
530.二叉搜索树的最小绝对差
2476.二叉搜索树最近节点查询
三种遍历方式的本质差异
在验证二叉搜索树（98 题）时，我分别用 先序 / 中序 / 后序 都实现了一遍，从而对三者有了更直观的理解。
先序遍历（Root → Left → Right）
特点：
- 在“访问当前节点”时，就已经掌握了关键信息
- 有机会提前返回，不一定遍历完整棵树
直观理解：
“我先看看当前节点行不行，再决定要不要往下走”
在某些 BST 题目中，这意味着剪枝能力强、效率高。
中序遍历（Left → Root → Right）
特点（BST 专属）：
- 中序遍历结果是一个严格递增的有序序列
直观理解：
“我不急着处理当前节点，先把左边都看完，保证顺序”
只要题目和“有序性 / 相邻关系 / 二分”有关，中序遍历往往是第一选择。
后序遍历（Left → Right → Root）
特点：
- 一定会遍历完整棵树
- 信息在子树返回时才产生
- 适合“自底向上”的问题
直观理解：
“我要先拿到左右子树的结果，才能决定当前节点的结果”
后序遍历是最通用、有返回值的一种方式。
不同题目中遍历方式的选择
理解三种遍历的本质后，再回头看具体题目，会发现“顺序选择”并不是随意的。
700. 二叉搜索树中的搜索 —— 先序遍历更优
核心原因：
- 一旦
root.val == target，可以立刻返回 - 完全没必要遍历无关子树
先序遍历在这里的优势是： “能提前命中并终止递归”
2️⃣ 938. 二叉搜索树的范围和 —— 先序 + 剪枝思想
题目要求：
计算所有值在
[low, high]范围内节点的和
关键观察（BST 性质）：
- 当前值
< low→ 只可能在右子树 - 当前值
> high→ 只可能在左子树 - 当前值在区间内 → 左右子树都可能有贡献
这使得解法可以在“访问当前节点”时直接决定递归方向，非常适合 先序遍历 + 提前返回。本质是： 在“递”的阶段就完成剪枝决策
530. 二叉搜索树的最小绝对差 —— 中序遍历
BST 中序遍历是严格递增序列，那么：
- 最小绝对差
- 一定只会出现在相邻两个节点之间
因此只需要：
- 中序遍历
- 记录前一个节点
- 比较当前值与前一个值的差
这是一个典型“利用 BST 有序性”的题目
2476. 二叉搜索树最近节点查询 —— 中序 + 二分
这道题让我收获最大的不是遍历本身，而是复杂度分析的思维。
两种思路对比
思路一：
- 每次查询都遍历整棵树
- 时间复杂度：
O(n × q)
思路二：
- 中序遍历 BST → 得到有序数组
- 对每个 query 在数组中二分查找
- 时间复杂度：
O(n + q log n)
为什么必须选思路二？
根据题目提示：
queries.length和节点数 n是同一个数量级
所以：
- 思路一 ≈
O(n²)（直接超时） - 思路二 ≈
O(n log n)（可接受）
结论：
当 BST 查询规模大、查询次数多时，一定要先转成有序数组（这种方式逻辑也很清晰，把逻辑都揉在树的遍历过程中十分复杂）
今天的核心学习总结
通过今天这组题目，我对二叉树遍历有了一个更“工程化”的理解：
- 遍历顺序的本质是“信息产生的时机”
- 先序遍历适合：提前判断、剪枝、搜索类问题
- 中序遍历在 BST 中有特性：有序性、相邻关系、二分优化
- 后序遍历最通用：自底向上、依赖子树返回值（今天体会不明显）
- 在数据规模较大时，复杂度分析往往比写法本身更重要
相关代码
本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。