应优先使用 std::set 替代手写 bst 实现区间提取，因其基于红黑树，支持 o(log n) 查找及 lower_bound/upper_bound，代码更安全简洁；手写需剪枝递归，避免退化为 o(n)；注意区分容器成员函数与算法版 upper_bound，后者对 set 迭代器性能劣化。
如何用 std::set 替代手写 BST 实现区间提取
绝大多数场景下，你不需要手写二叉搜索树来提取区间——std::set 内部就是红黑树，天然支持有序、去重、O(log n) 查找，且自带 lower_bound 和 upper_bound。直接用它，代码更短、更安全、更难出错。
常见错误是执着于“必须手写 BST”，结果在递归边界、指针空检查、内存泄漏上反复踩坑。而 std::set 的区间提取只需两行：
auto left = s.lower_bound(low); auto right = s.upper_bound(high); std::vector<int> result(left, right); </int>
-
lower_bound(low)返回第一个 ≥low的迭代器 -
upper_bound(high)返回第一个 >high的迭代器，正好作为右开区间终点 - 构造
vector时使用迭代器区间，自动截取 [low,high] 内所有值
手写 BST 中实现 rangeQuery 的递归逻辑怎么写
如果教学或面试要求必须手写，核心不是遍历整棵树，而是剪枝：只进入可能含目标值的子树。关键判断是当前节点值与区间的关系。
假设节点结构为 struct Node { int val; Node* left; Node* right; };，递归函数签名应为 void rangeQuery(Node* root, int low, int high, std::vector<int>& res)</int>：
- 若
root == nullptr，直接返回 - 若
root->val ，说明左子树全小于 <code>low，只递归右子树 - 若
root->val > high，说明右子树全大于high，只递归左子树 - 否则
low ≤ root->val ≤ high，当前节点入结果，再分别递归左右子树
漏掉剪枝条件会导致时间退化成 O(n)，尤其当区间很窄但树很深时。
std::set::upper_bound 和 std::upper_bound（算法版）的区别
这是最容易混淆的点：前者是容器成员函数，后者是泛型算法，行为不同。
-
s.upper_bound(x)在std::set上是O(log n)，利用红黑树结构快速跳转 -
std::upper_bound(first, last, x)要求迭代器支持随机访问（如vector::iterator），对set::iterator使用会退化成O(n)—— 因为set迭代器是双向的，不支持+运算 - 所以绝不能写
std::upper_bound(s.begin(), s.end(), x)；必须用s.upper_bound(x)
编译器通常不会报错，但运行时性能骤降，调试时很难定位。
区间提取结果要不要保留原始插入顺序
BST / std::set 天然按值升序排列，提取结果一定是升序。如果你需要按插入顺序（即“在区间内，谁先插进来谁排前面”），BST 本身无法满足。
- 方案一：额外维护一个
std::list<int></int>记录插入序列，再用unordered_set快速判断是否在区间内 —— 空间换逻辑清晰 - 方案二：改用
std::vector+ 手动排序 + 二分查找，但插入变慢，且需自行处理重复 - 方案三：接受升序结果 —— 绝大多数业务场景中，“区间内所有值”本就隐含有序语义
别为了“看起来像原顺序”强行加复杂度，先确认需求是否真需要它。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
