二叉搜索树区间查询的核心逻辑是利用BST左小右大的结构性质剪枝，避免中序遍历全树。递归时根据当前节点值与[low, high]关系决定是否进入左右子树：若root->val >= low则递归左子树，若root->val <= high则递归右子树。
二叉搜索树区间查询的核心逻辑是什么
直接说结论：不能简单中序遍历全树再过滤，必须利用 BST 左小右大的结构性质剪枝，否则退化成 O(n)。关键在于递归时根据当前节点值和目标区间 [low, high] 决定是否进入左右子树。
如何写一个高效的 rangeQuery 递归函数
常见错误是忽略边界条件导致重复访问或漏节点，比如把 root->val == low 当作终止条件，其实它本身要被包含；或者误判子树完全无关而跳过——哪怕 root->val ，右子树仍可能有满足条件的节点。
- 若
root为空，直接返回 - 若
root->val > low，左子树可能含有效值，递归查左 - 若
root->val ，右子树可能含有效值，递归查右 - 若
low val ，当前节点加入结果（注意不是“仅此时才查子树”，子树仍需按上两条判断）
示例片段（返回 vector）：
void rangeQuery(TreeNode* root, int low, int high, vector<int>& res) {
if (!root) return;
if (root->val > low) rangeQuery(root->left, low, high, res);
if (root->val >= low && root->val <= high) res.push_back(root->val);
if (root->val < high) rangeQuery(root->right, low, high, res);
}
rangeQuery 的性能与边界陷阱
最坏仍是 O(n)，但平均接近 O(k + log n)，k 是区间内节点数。容易踩的坑集中在边界处理：
立即学习“C++免费学习笔记（深入）”；
- 用
<和<=混淆：比如写成if (root->val < low)就跳过左子树，错——应是> low才说明左子树可能还有值 - 把
low == high当特殊 case 单独处理，没必要，通用逻辑自然覆盖 - 传参时误传
low和high顺序颠倒，函数没校验，结果为空——建议调用前断言low <= high - 如果需要返回迭代器或支持流式处理，别一次性 collect 到 vector，改用回调函数参数
std::function<void(int)> visit
要不要用非递归方式实现
可以，但不推荐初学者优先尝试。栈模拟递归时，每个入栈节点需附带其对应的有效区间（即该子树实际可贡献的 [l, r] 范围），否则无法正确剪枝。比如根节点区间是 [INT_MIN, INT_MAX]，进左子树时新区间变成 [l, root->val - 1]，进右子树是 [root->val + 1, r]。稍一疏忽就漏节点或越界。
真正需要非递归的场景通常是栈深度受限或要求严格尾递归优化，一般情况递归更直观、不易错。
