二叉搜索树的区间查询是给定闭区间[low, high]，返回所有值落在该区间的节点；它利用bst左小右大性质剪枝跳过整棵无关子树，平均时间复杂度为o(k + log n)，而非暴力遍历的o(n)。
什么是二叉搜索树的区间查询，它和普通遍历有什么区别
区间查询不是简单地中序遍历再过滤——那样时间复杂度是 O(n)，完全浪费了 BST 的结构优势。真正高效的区间查询应只访问可能落在 [low, high] 内的节点，跳过明显无关的子树。核心判断依据就一条：若当前节点值 val ，则左子树全小于 <code>low，可直接剪枝；若 val > high，则右子树全大于 high，同样跳过。
如何递归实现带剪枝的区间提取（C++）
用一个 std::vector<int></int> 传引用收集结果，避免频繁拷贝。递归函数需明确三个分支逻辑：
- 当前节点为空 → 直接返回
- 当前值
val → 只递归右子树（左子树全无效） - 当前值
val > high→ 只递归左子树（右子树全无效） - 否则（
low ）→ 先取当前值，再左右子树都递归
示例片段：
void rangeQuery(Node* root, int low, int high, std::vector<int>& res) {
if (!root) return;
if (root->val right, low, high, res);
} else if (root->val > high) {
rangeQuery(root->left, low, high, res);
} else {
res.push_back(root->val);
rangeQuery(root->left, low, high, res);
rangeQuery(root->right, low, high, res);
}
}</int>
迭代写法要注意栈里存什么节点
迭代不是简单套用中序模板。必须在入栈前做剪枝判断，否则栈里塞满无效节点。关键点在于：只把「可能包含目标区间内节点」的子树根推入栈。
- 从根开始，若
cur->val >= low，才把cur->left入栈（因为左子树可能还有 ≥ low 的节点） - 若
cur->val ，才把 <code>cur->right入栈（右子树可能还有 ≤ high 的节点） - 每次出栈后，仅当
low val 才加入结果
漏掉任一条件就会导致重复访问或遗漏边界值。
为什么 std::set 或 std::map 不能直接替代手写 BST 区间查询
它们底层虽是红黑树，但标准库没暴露内部结构，lower_bound 和 upper_bound 只能拿到迭代器范围，无法控制遍历路径剪枝。更关键的是：如果你的 BST 节点还存有额外字段（如子树大小、颜色、自定义元数据），而你需要在区间查询中动态利用这些信息（比如查第 k 小且在 [low, high] 内的数），那必须手写并维护这些扩展属性——标准容器做不到。
实际编码时最容易忽略的是边界相等的处理，比如 low == high 时是否仍要进入双侧递归；还有空指针检查位置不对，导致段错误。这些细节不跑测试很难暴露。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
