二叉搜索树的区间查询是找出所有满足low ≤ key ≤ high的节点，区别于普通遍历的关键在于利用BST左小右大性质剪枝跳过整棵无关子树，避免O(n)暴力遍历，平均时间复杂度降至O(k + log n)。
什么是二叉搜索树的区间查询，它和普通遍历有什么区别？
区间查询不是找单个值，而是找出所有 key 满足 low ≤ key ≤ high 的节点。直接中序遍历再过滤当然可行，但会访问大量无关子树（比如当前节点已大于 high，右子树全可跳过），效率低且无法提前剪枝。
关键判断是：BST 的结构天然支持剪枝，必须利用左小右大的性质跳过整棵子树。否则写成“遍历 + 条件判断”，就等于放弃了 BST 的核心优势。
如何递归实现带剪枝的区间查询？
核心逻辑是根据当前节点值与区间边界的关系，决定是否进入左右子树：
- 如果
node->val < low，说明左子树全小于low，无需访问；只递归右子树 - 如果
node->val > high，说明右子树全大于high，无需访问；只递归左子树 - 如果
low ≤ node->val ≤ high，当前节点命中，左右子树都可能含有效节点，需递归两边
void rangeQuery(Node* root, int low, int high, vector<int>& result) {
if (!root) return;
if (root->val < low) {
rangeQuery(root->right, low, high, result);
} else if (root->val > high) {
rangeQuery(root->left, low, high, result);
} else {
result.push_back(root->val);
rangeQuery(root->left, low, high, result);
rangeQuery(root->right, low, high, result);
}
}
注意：顺序不能颠倒——必须先判断越界再决定走哪边，否则会漏掉边界节点（比如 root->val == low 时，仍需查左子树，因为左子树可能有等于 low 的重复值，或更小但仍在区间内的值——不过标准 BST 通常无重复，但逻辑上要覆盖）。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
迭代写法怎么避免栈爆掉或逻辑错乱？
递归简洁，但深度过大时可能栈溢出。迭代需手动维护待处理节点，关键是入栈前做剪枝判断，而不是无脑把左右孩子都压入：
- 当前节点为空 → 跳过
- 当前节点值 <
low→ 只将右孩子入栈（左子树全废） - 当前节点值 >
high→ 只将左孩子入栈（右子树全废） - 否则 → 当前节点加入结果，左右孩子都入栈（但各自入栈前仍要独立判断剪枝）
vector<int> rangeQueryIterative(Node* root, int low, int high) {
vector<int> result;
stack<Node*> stk;
if (root) stk.push(root);
while (!stk.empty()) {
Node* node = stk.top(); stk.pop();
if (!node) continue;
if (node->val < low) {
if (node->right) stk.push(node->right);
} else if (node->val > high) {
if (node->left) stk.push(node->left);
} else {
result.push_back(node->val);
if (node->left) stk.push(node->left);
if (node->right) stk.push(node->right);
}
}
return result;
}
常见错误是把“入栈”和“是否处理当前节点”混在一起，导致重复添加或漏加。务必记住：只有满足 low ≤ val ≤ high 才 push_back，其它情况只转发子节点（且仅转发可能有效的那个）。
如果 BST 含重复值或需要返回指针/自定义对象怎么办？
标准 BST 定义不允许重复键，但实际场景常允许（如用 multiset 底层或手动实现）。此时要注意：
- 查询逻辑不变，剪枝条件仍基于比较，但需确认比较函数是否严格（
<vs<=） - 若需返回
Node*而非值，直接存指针即可，但注意生命周期管理（别返回局部树的临时指针） - 若节点含复杂数据（如
struct Record { int id; string name; }），确保operator<或比较函数只基于用于 BST 排序的字段（通常是id），否则区间语义失效
最容易被忽略的是：区间查询结果不保证有序，除非你按中序路径收集（上述递归写法天然有序，迭代版需额外排序或改用中序模拟）。如果业务要求升序输出，别依赖迭代版的 result 顺序——它取决于入栈顺序，不是自然有序。
