如何在二叉搜索树中输出某个区间内的所有节点值？

简化版

利用 BST 有序性做剪枝：若当前值大于下界，左子树可能还有区间内值；若当前值在 [low, high] 内，输出它；若当前值小于上界，右子树可能还有区间内值。按左、根、右顺序处理，结果天然升序。

详细版

普通二叉树要遍历所有节点才能找区间值。BST 可以剪枝：

node.val < low：左子树更小，一定不在区间，只查右子树；
node.val > high：右子树更大，一定不在区间，只查左子树；
low <= node.val <= high：左右两边都可能有结果，按中序输出。

常见代码：

若 node == null 返回；
若 node.val > low，递归左子树；
若当前值在区间内，加入答案；
若 node.val < high，递归右子树。

时间复杂度可写成 O(h+k)，k 是输出个数；最坏 O(n)。空间复杂度 O(h)。

完整版教学

一、区间查询为什么是 BST 的典型能力

BST 不只支持查找单个值，还天然适合范围查询。因为任意节点都把整棵树切成左小右大两部分，所以我们可以根据当前值和区间 [low, high] 的关系，判断某些子树是否完全不可能包含答案。

比如区间是 [5,10]，当前节点值是 3。它的左子树都小于 3，更不可能达到 5，所以左子树整棵都可以跳过，只去右子树。这个「整棵跳过」就是剪枝带来的效率。

记忆钩子：BST 区间查询像拿尺子卡范围，整棵太小就往右，整棵太大就往左，卡中间才左右都看。

二、三种位置关系怎么剪枝

当前值与区间有三种关系：

当前值位置	左子树	当前节点	右子树
`val < low`	全部更小，剪掉	不输出	可能有答案
`low <= val <= high`	可能有答案	输出	可能有答案
`val > high`	可能有答案	不输出	全部更大，剪掉

这个表就是代码的来源。注意不是只有当前节点在区间内才访问左右子树；当 val < low 时，右子树仍可能进入区间；当 val > high 时，左子树仍可能进入区间。

三、为什么中序输出天然升序

如果题目要求升序输出，按中序框架写最自然：先处理可能的左子树，再处理当前节点，再处理可能的右子树。因为 BST 的中序结果是升序，剪枝只是跳过不需要的子树，不会打乱剩余节点的相对顺序。

void rangeSearch(TreeNode node, int low, int high, List<Integer> ans) {
    if (node == null) return;
    if (node.val > low) {
        rangeSearch(node.left, low, high, ans);
    }
    if (node.val >= low && node.val <= high) {
        ans.add(node.val);
    }
    if (node.val < high) {
        rangeSearch(node.right, low, high, ans);
    }
}

这里用 > 和 < 决定是否查左右子树。若允许重复值并且重复值可能放在左或右，等号是否剪掉要根据重复值规则确认。

四、带数字例子看剪枝效果

假设中序为 [1,3,4,6,8,9,12,15]，查询 [4,9]。访问根 8 时在区间内，左右都可能有答案；访问右子树 12 时，12 > 9，所以它的右子树如 15 整个剪掉；访问左侧 3 时，3 < 4，所以它的左子树如 1 整个剪掉。

区间 [4,9]
val=3  -> 太小，跳过左子树
val=8  -> 输出，并查两边
val=12 -> 太大，跳过右子树

如果树平衡且区间很窄，剪枝能跳过大量节点；如果区间覆盖全树，就退化成完整中序遍历。

五、复杂度为什么常写 O(h+k)

理想情况下，搜索会先沿树高找到区间边界附近，再输出区间内的 k 个节点，并只访问少量边界路径节点。因此可以说复杂度接近 O(h+k)。但在最坏情况下，例如树退化或区间覆盖大部分节点，仍可能访问 O(n) 个节点。

h: 为找到区间边界付出的路径成本
k: 真实输出的节点数量
最坏: k=n 或树严重退化 -> O(n)

面试中可以表达为「时间 O(h+k)，最坏 O(n)」。这比只说 O(n) 更能体现你理解剪枝收益，也比绝对说 O(log n + k) 更严谨。

六、和范围求和有什么区别

范围求和只需要累加值，不关心输出顺序；范围输出通常需要保持升序。因此范围求和可以先判断当前节点是否太小或太大，再递归对应方向；范围输出更适合保留中序结构。两者剪枝条件相似，但输出动作不同。

题型	目标	是否需要升序	常用写法
区间求和	返回 sum	否	DFS 剪枝累加
区间输出	返回列表	通常是	中序剪枝
区间计数	返回 count	否	DFS 剪枝或带 size 增强

如果 BST 节点额外维护子树 size 或 sum，还能把区间计数/求和进一步优化，这是进阶方向。

七、常见误区与追问

误区：当前节点不在区间就两边都不用看。 若当前值太小，右边可能有；若当前值太大，左边可能有。
追问：为什么输出是升序？ 因为采用了中序遍历，只是剪掉不可能的子树。
误区：区间查询一定是 O(log n)。 还要输出 k 个结果，至少 O(k)，树退化时最坏 O(n)。
追问：重复值在边界上怎么办？ 要看重复值放置规则，必要时等于 low/high 的方向不能直接剪掉。
误区：范围求和和范围输出代码完全一样。 求和不关心顺序，输出通常要按中序保证升序。

八、加强记忆

BST 区间输出的口诀是「大于 low 才看左，小于 high 才看右，自己在范围内就输出」。这三个条件直接来自左小右大的性质。按中序写，答案天然升序；靠剪枝跳过整棵不可能的子树。复杂度别说死成 O(log n)，因为输出 k 个元素本身就要 O(k)，最坏还可能访问全树。

简化版

详细版