递归中序遍历BST可高效提取[low, high]区间值，利用BST性质剪枝：val < low时跳过左子树，val > high时跳过右子树，仅在low ≤ val ≤ high时收集；标准库upper_bound等可简化实现，但需注意比较逻辑中等号缺失易致空结果误判。
如何用递归中序遍历提取 BST 中指定范围内的所有值
中序遍历天然产出升序序列，是提取 [low, high] 区间值最直观的方式。但直接遍历整棵树再过滤会浪费时间——BST 的结构允许提前剪枝。
- 遇到
node->val 时，左子树全小于 <code>low，可跳过整个左子树，只递归右子树 - 遇到
node->val > high时，右子树全大于high，可跳过整个右子树，只递归左子树 - 否则（
low val ），当前节点加入结果，并递归左右子树
示例核心逻辑：
void rangeQuery(Node* root, int low, int high, vector<int>& res) {
if (!root) return;
if (root->val >= low && root->val <= high) {
rangeQuery(root->left, low, high, res);
res.push_back(root->val);
rangeQuery(root->right, low, high, res);
} else if (root->val < low) {
rangeQuery(root->right, low, high, res);
} else { // root->val > high
rangeQuery(root->left, low, high, res);
}
}为什么不用迭代版中序遍历做区间查询
迭代中序需要显式维护栈，而区间剪枝会破坏“统一入栈-出栈”流程：你不能简单地把所有左链节点压栈，因为某节点被剪枝后，其右子树是否该访问取决于父节点值是否落在区间内，逻辑耦合变强。
- 递归天然携带上下文（当前节点值、父子关系），剪枝判断直接、无副作用
- 迭代实现若强行支持剪枝，需在每步弹栈后额外判断是否进入右子树，代码易错且可读性下降
- 除非明确要求避免递归栈溢出（如超深树），否则递归更稳妥
std::set 能否替代手写 BST 实现区间查询
可以，而且更推荐——std::set 底层是红黑树，支持 lower_bound 和 upper_bound，能 O(log n) 定位区间起点和终点，再用迭代器线性遍历区间内元素，整体复杂度 O(k + log n)，k 是结果数量。
立即学习“C++免费学习笔记（深入）”；
-
auto it1 = s.lower_bound(low);找第一个 ≥low的元素 -
auto it2 = s.upper_bound(high);找第一个 >high的元素 - 然后
for (auto it = it1; it != it2; ++it)即得全部匹配值 - 注意：
upper_bound返回的是开区间上界，正好配合!=终止条件
比手写 BST 省去内存管理、旋转逻辑、边界 null 判断等细节，且标准库经过充分测试。
区间查询结果为空时的常见误判点
容易把空结果归因于“树为空”或“范围不合理”，但真实原因常是节点值比较逻辑写错，尤其是符号方向或等号缺失。
- 写成
if (val > low && val 会漏掉端点值，应为 <code>>=和<= - 调用
lower_bound时传入high而非high+1，导致upper_bound位置偏移 - 递归基没处理
nullptr，导致段错误而非空结果 - 容器类型选错：用
std::vector接收但未清空，残留上次查询结果
调试时优先打日志输出 low、high、当前节点 val 和剪枝分支选择，比单步跟递归更高效。
