LeetCode 938. 二叉搜索树的范围和

2022-01-25 HGNULB 约 9 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 938. 二叉搜索树的范围和

题意分析

给一棵二叉搜索树的根节点 root 和闭区间 [low, high]，把树中所有落在这个区间内的节点值加起来返回。注意是闭区间，low 和 high 本身若存在于树中也要计入。

题目特意强调了「二叉搜索树」而不是普通二叉树，这是全题唯一的信号。普通二叉树只能老老实实访问每个节点，而 BST 多出一条全局性质：任意节点的左子树所有值都小于它，右子树所有值都大于它。这条性质意味着只看当前节点的值就能对整棵子树下判断，而不需要走进去看。

顺着这条信号往下推：如果当前节点值小于 low，那它的整棵左子树都比它还小，必然全部小于 low，一个都不可能有贡献；对称地，如果当前节点值大于 high，右子树可以整体丢弃。能整体丢弃子树，就说明这题期待的是一个带剪枝的遍历，而不是全量遍历后过滤。

边界方面要留意三处：空树返回 0；节点值恰好等于 low 或 high 时必须计入；题目保证节点值互不相同，所以不用担心区间内重复计数的问题。另外值域可以到 $10^5$、节点数也可到 $2 \times 10^4$，累加和会超过单个节点值的范围但仍在 int 内，不必上 long。

还有一点容易被忽略：题目没有保证区间内的节点在树中是连续的一段，也没有保证 low、high 一定存在于树中，所以不能写成「先找到 low 再中序走到 high」那种依赖端点存在的写法。

解法：DFS + BST 剪枝

核心思路

最朴素的做法是把树当普通二叉树，完整遍历一遍，对每个节点判断 low <= val <= high，是就累加。这在 $O(n)$ 时间内也能过，但它完全没有用到「搜索树」这个前提——如果把树的所有值随机打乱重排，这份代码依然成立，说明它没有抓住题目给的信息。

瓶颈就在这里：全量遍历会走进大量明知不可能有贡献的子树。比如区间是 [7, 15]，而某个节点值为 3，那它左子树里全是小于 3 的数，这些节点被访问了却一个也没被累加，纯属浪费。

观察的关键是把「一个节点的值」提升为「一整棵子树的值域约束」。设 dfs(node) 表示以 node 为根的子树中，落在 [low, high] 内的节点值之和。由 BST 性质可知：

若 node.val < low，则 node 及其整棵左子树的值都 < low，因此 dfs(node) = dfs(node.right)；

若 node.val > high，则 node 及其整棵右子树的值都 > high，因此 dfs(node) = dfs(node.left)；

否则 low <= node.val <= high，当前节点计入，两侧子树都可能有贡献，dfs(node) = node.val + dfs(node.left) + dfs(node.right)。

这三条就是完整的递归定义，它们互斥且覆盖了所有情况，因此不需要额外的分支。递归的不变量是：dfs(node) 的返回值永远等于「该子树中区间内节点值之和」，与调用它的上层处于哪个分支无关——这一点保证了三条规则可以随意组合而不会重复或遗漏计数。

值得强调的是，第一条和第二条规则里被剪掉的不是「一个节点」，而是「一整棵子树」，这才是剪枝的价值所在。第三条规则里两边都要递归，是因为当前节点在区间内时，左子树中仍可能有小于 low 的节点、右子树中仍可能有大于 high 的节点，必须继续往下判断。

解题步骤

定义递归函数的语义：dfs(node, low, high) 返回 node 子树中区间内节点值之和。先把语义写死，后面每一个分支都只需检查「返回值是否符合这个语义」，不会写着写着混淆。

递归基：node == null 返回 0。为什么用 0 而不是特判父节点的子指针：空子树的区间和天然就是 0，用它做单位元可以让上层的加法与替换式返回都无须特判，代码只有一个出口分支。

左剪枝：node.val < low 时直接 return dfs(node.right, ...)。为什么可以整棵左子树都不看：BST 保证左子树全部小于 node.val，而 node.val 已经小于 low，传递下去左子树全部小于 low，贡献恒为 0；当前节点自己也不在区间内，所以不加 node.val。

右剪枝：node.val > high 时直接 return dfs(node.left, ...)。理由与上一条对称。

命中区间：剩下的情况必然满足 low <= node.val <= high，返回 node.val + dfs(left) + dfs(right)。为什么两边都要继续递归：当前节点在区间内只说明它自己合法，左子树里仍可能藏着比 low 小的节点、右子树里仍可能藏着比 high 大的节点，剪枝要交给更深层去做。

注意判断用的是非严格边界：写 node.val < low 而不是 <=，写 node.val > high 而不是 >=，这样等于端点的节点会落进第三个分支被计入，正好对应闭区间语义。

以 root = [10,5,15,3,7,null,18]、low = 7、high = 15 走一遍。这棵树是：根 10，左孩子 5（左 3、右 7），右孩子 15（右 18）。

dfs(10)：10 在 [7, 15] 内，命中第三条，结果为 10 + dfs(5) + dfs(15)。
dfs(5)：5 < 7，命中左剪枝，节点 3 整棵子树被跳过，结果为 dfs(7)。
dfs(7)：7 在区间内（这里正是端点，用 < 而非 <= 才能保住它），结果为 7 + dfs(null) + dfs(null) = 7。所以 dfs(5) = 7。
dfs(15)：15 在区间内（另一个端点），结果为 15 + dfs(null) + dfs(18)。
dfs(18)：18 > 15，命中右剪枝，结果为 dfs(null) = 0。所以 dfs(15) = 15。
回到根：10 + 7 + 15 = 32，与预期一致。整个过程访问了 10、5、7、15、18 五个节点，节点 3 一次都没被访问，剪枝生效。

代码实现

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)
}

复杂度分析

时间复杂度：最坏 $O(n)$，实际远小于此。凭什么：每个被访问的节点只做常数次比较与加法，且每个节点至多被访问一次；当区间覆盖整棵树时无法剪枝，退化为全量遍历，故上界为 $O(n)$；区间较窄时被剪掉的子树完全不进入递归，实际访问量约为「区间内节点数 + 两条边界搜索路径」。

空间复杂度：$O(h)$，h 为树高。凭什么：除了递归调用栈没有开辟任何辅助结构，栈深度等于当前递归路径长度，最多为树高；平衡时为 $O(\log n)$，退化成链时为 $O(n)$。

关键点总结

BST 的核心价值是「用一个节点的值给一整棵子树的值域定界」，凡是题目点明 BST，第一反应就该是找哪些子树可以整体排除，而不是先想怎么遍历。

把递归函数的返回值语义先写成一句话（「该子树中区间内节点值之和」），再逐条推分支，是写树形递归最省心的顺序；分支写乱通常是因为语义没定死。

空节点返回 0 属于「用单位元消灭特判」的通用手法，同类的还有空子树深度返回 0、空子树最大值返回负无穷。

闭区间与开区间的差别全落在比较符的等号上，写代码前先把题面的区间开闭读准，比事后调试快得多。

面试视角：写完剪枝版后主动说明「不剪枝的全量遍历也是 $O(n)$，但剪枝版在窄区间下实际访问量小得多，而且能体现对 BST 性质的理解」，这是面试官在这道简单题上真正想听的点；若被追问进阶，可以提中序遍历天然有序、可以在遍历到超过 high 时提前终止。

同一套「按值域剪枝」的思路可以直接迁移到 BST 上的查找、插入、删除与区间查询，模板高度一致。

易错点总结

错误写法：把剪枝条件写成 node.val <= low → 用例 root = [10,5,15,3,7,null,18]、low = 7、high = 15 中，节点 7 会被当成越界而跳过自身，答案从 32 变成 25。

错误写法：把 node.val > high 写成 >= → 同一用例中节点 15 被跳过，答案从 32 变成 17。

错误写法：左剪枝时写成 return node.val + dfs(node.right, ...) → 用例 low = 7 时节点 5 明明不在区间内却被累加，答案多出 5。

错误写法：左剪枝时误递归左子树 return dfs(node.left, ...) → 用例中从节点 5 走向节点 3，越走越小，区间内的节点 7 永远访问不到，答案漏掉 7。

错误写法：忘记 node == null 的递归基 → 用例中递归到节点 18 的空左孩子时直接空指针异常（Go 里是 nil 解引用 panic）。

错误写法：命中区间时只递归一侧，比如 node.val + dfs(node.left, ...) → 用例中根节点 10 命中区间后不再看右子树，节点 15 丢失，答案变成 17。

错误写法：把三个分支写成 if / if / if 且前两个分支不 return，落到最后统一累加 → 剪枝分支的结果被丢弃后又执行了第三条规则，节点 5、18 被重复计入，答案变成 55。

错误写法：用一个成员变量累加而不是靠返回值传递，且多组测试用例复用同一个 Solution 实例 → 第二次调用时上一次的和没清零，结果被叠加放大。

错误写法：假设 low、high 一定存在于树中，先二分找到 low 的位置再中序累加到 high → 用例 low = 6、high = 16 时找不到起点，逻辑直接落空返回 0。

相似题目

题目	难度	考察点
700. 二叉搜索树中的搜索	简单	同样按值比较决定走哪一侧，但只需单侧下沉，不存在两侧都递归的情况
701. 二叉搜索树中的插入操作	中等	从「读」变成「写」，要在空位处挂上新节点并把子指针接回父节点
450. 删除二叉搜索树中的节点	中等	定位后还要处理双子节点的前驱/后继替换，是 BST 修改类里最复杂的一档
98. 验证二叉搜索树	中等	反过来用值域：向下传递 `(min, max)` 上下界校验，而非用值域剪枝
230. 二叉搜索树中第 K 小的元素	中等	依赖的是中序遍历有序性与计数提前返回，而不是子树整体排除
1038. 从二叉搜索树到更大和树	中等	反向中序累加并原地改值，考的是遍历次序而非剪枝
653. 两数之和 IV - 输入二叉搜索树	简单	需要跨节点配对，单纯的子树剪枝不成立，得配哈希集合或双指针