LeetCode 938. 二叉搜索树的范围和
题目描述
题意分析
求二叉搜索树中节点值落在闭区间
[low,high]内的总和，等于任意边界的节点也要计入。树的有序性允许一次排除整棵不可能命中的子树，而不必逐个检查其中节点。
解法：DFS + BST 剪枝
核心思路
[!blue]
定义
dfs(node)返回以当前节点为根的子树中，所有合格节点的值之和。空子树没有贡献，返回0；非空节点按它与查询区间的关系分成三种情况。若
node.val < low，当前节点不合格，左子树所有值还更小，也都小于low，所以当前节点和整棵左子树的贡献都是零，只需返回右子树的查询结果。若node.val > high，同理排除当前节点和整棵右子树，只搜索左子树。若当前值位于区间内，就计入它，再加上左右子树各自的查询结果。此时不能直接把整棵子树都计入，因为更小的后代仍可能低于
low，更大的后代也可能高于high，需要继续按同一规则筛选。三种情况覆盖了全部可能：剪掉的子树确定没有贡献，保留的左右子树与当前节点互不重叠。只要递归正确返回较小子树的区间和，就能组合出当前子树的正确答案；递归最终到达空节点，因此既不漏算也不重复累加。
解题步骤
- 空节点返回零。
- 当前值小于下界时，只递归右子树。
- 当前值大于上界时，只递归左子树。
- 否则累加当前值与两侧区间和。
没有节点落入区间时，各分支最终返回的都是零；查询包含全树值域时，所有节点都会计入。即使
low==high，严格的越界判断也会保留恰好等于该值的节点。
代码实现
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
return dfs(root, low, high);
}
private int dfs(TreeNode node, int low, int high) {
if (node == null) {
return 0;
}
// 当前值小于下界，左子树只会更小，整棵跳过。
if (node.val < low) {
return dfs(node.right, low, high);
}
// 当前值大于上界，右子树只会更大，整棵跳过。
if (node.val > high) {
return dfs(node.left, low, high);
}
return node.val + dfs(node.left, low, high) + dfs(node.right, low, high);
}
}
func rangeSumBST(root *TreeNode, low int, high int) int {
if root == nil {
return 0
}
// 当前值小于下界，左子树只会更小，整棵跳过。
if root.Val < low {
return rangeSumBST(root.Right, low, high)
}
// 当前值大于上界，右子树只会更大，整棵跳过。
if root.Val > high {
return rangeSumBST(root.Left, low, high)
}
return root.Val + rangeSumBST(root.Left, low, high) + rangeSumBST(root.Right, low, high)
}
复杂度分析
- 时间复杂度：设区间内节点数为
k、树高为h，访问量为 $O(k+h)$。合格节点各访问一次，区间外仍被访问的节点位于查找两个边界的路径上；最坏仍为 $O(n)$。- 空间复杂度：$O(h)$，用于递归调用栈；退化成链时最坏为 $O(n)$。
关键点总结
[!green]
- 剪枝依据是整棵子树的值域，不只是一个孩子。
- 区间包含两端，等于 low 或 high 的节点必须计入。
- 返回值统一表示当前子树的有效总和。
易错点总结
[!yellow]
- 用
<=low或>=high排除节点，会漏掉闭区间边界。- 越界时只返回可能命中一侧的递归结果，不能再加入当前节点值。
- 当前节点合格不代表全部后代合格，两侧仍需递归判断。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 669. 修剪二叉搜索树 | 中等 | 同样利用BST范围关系剪掉不可能贡献的子树，原题修改树，本题只累计范围内节点值。 |
| 700. 二叉搜索树中的搜索 | 简单 | 点查找扩展成区间查询，当前值小于下界时只需查右子树，大于上界时只需查左子树。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！