如何求二叉搜索树中指定区间的节点和？

简化版

利用 BST 的大小关系做剪枝：如果当前节点值小于 low，左子树更小，不可能进入区间，只搜右子树；如果当前节点值大于 high，右子树更大，不可能进入区间，只搜左子树；否则当前节点在区间内，加上左右子树的区间和。

详细版

普通二叉树求区间和只能遍历所有节点，时间 O(n)。BST 可以利用有序性少走很多无效分支：当前节点 node.val < low 时，它的左子树所有节点都更小，因此整棵左子树都可以跳过；当前节点 node.val > high 时，它的右子树所有节点都更大，因此整棵右子树都可以跳过。

递归写法很自然：空节点返回 0；小于下界时返回右子树结果；大于上界时返回左子树结果；落在 [low, high] 内时返回 node.val + left + right。最坏时间 O(n)，但在平衡且区间较窄时通常只访问和区间相关的路径与节点。

完整版教学

一、这题真正考的是 BST 剪枝

区间求和本身不难，难点在于不要把 BST 当普通二叉树暴力扫。BST 的节点值满足左小右大，因此当前节点一旦低于区间下界，它左边的所有节点只会更低；当前节点一旦高于区间上界，它右边的所有节点只会更高。这个性质可以把一整片子树直接排除。

如果 node.val < low:
  left subtree < node.val < low
  左子树全部无效，只去右边

如果 node.val > high:
  right subtree > node.val > high
  右子树全部无效，只去左边

这就是剪枝的含义：不是访问后再判断要不要加，而是在确定一棵子树不可能贡献答案时，连访问都不访问。

二、用一个具体例子看剪枝收益

假设 BST 为 [10,5,15,3,7,null,18]，区间是 [7, 15]，答案应为 7 + 10 + 15 = 32。

        10
       /  \
      5    15
     / \     \
    3   7     18

low = 7, high = 15

从 10 开始，10 在区间内，左右都可能有贡献；到 5 时，5 < 7，所以 5 的左子树 3 更小，直接跳过，只看右子树 7；到 15 时，15 在区间内，但它的右子树 18 > 15，可以跳过。最终只访问 10、5、7、15、18 中必要路径，3 完全不用看。

三、递归状态如何设计

这题不需要额外全局变量，函数本身就可以返回“以当前节点为根的子树中，落在区间内的节点和”。递归语义清楚后，三种情况就很稳定。

int rangeSumBST(TreeNode root, int low, int high) {
    if (root == null) 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);
}

注意判断顺序里 < low 和 > high 是剪枝分支，只有落入区间时才左右都递归。把这三个分支写反不会影响某些样例，但会让剪枝失效，甚至漏加边界节点。

四、区间边界为什么是闭区间

常见题目给的是 low 和 high，要求包含边界值，所以判断应该是 low <= node.val <= high。例如区间 [7,15] 中，节点 7 和节点 15 都要被加入答案。若写成 node.val <= low 就去右边，会把等于 low 的节点漏掉。

当前值	区间 `[7,15]` 下的处理	原因
5	只搜右子树	当前值和左子树都小于 7
7	加入答案，并继续搜左右	7 是合法边界
10	加入答案，并继续搜左右	落在区间内部
15	加入答案，并继续搜左右	15 是合法边界
18	只搜左子树	当前值和右子树都大于 15

边界题是面试官最爱追的地方，因为它能检验你到底是在背模板，还是理解了闭区间和 BST 剪枝条件。

五、复杂度不能只写 O(log n)

最坏情况下，区间覆盖整棵树，比如 [−10^9, 10^9]，每个节点都要被加一次，时间就是 O(n)。如果树退化成链表，也可能访问很多节点。更合理的表达是：最坏 O(n)，空间 O(h)；在平衡树且区间较窄时，剪枝能跳过大量无关子树。

最坏访问节点数：n
递归栈深度：h
平衡树：h = O(log n)
退化树：h = O(n)

如果面试官继续追问“能不能更快”，要先说明对普通 BST 单次查询，必须沿路径确认边界附近节点；如果需要大量区间和查询，可以在平衡树节点上维护子树和，变成增强 BST 或使用线段树、树状数组等结构。

六、常见误区与追问

看到区间题先想：当前节点太小，砍左；当前节点太大，砍右；落入区间，左右都看。

误区：每个节点都递归左右，再判断是否加当前值。 这样功能能对，但没有利用 BST，复杂度退化为普通 DFS。
误区：root.val == low 时直接去右边。 区间通常是闭区间，等于 low 的节点必须加入答案。
误区：当前节点在区间内时只沿一个方向走。 左右子树都可能还有区间内节点，例如 10 的左边可能有 7，右边可能有 15。
追问：为什么 root.val < low 可以跳过左子树？ 因为左子树所有节点都小于 root.val，自然也小于 low。
追问：最坏复杂度是多少？ 最坏 O(n)，不是固定 O(log n)，因为区间可能覆盖所有节点。
追问：多次区间求和怎么优化？ 可以维护子树节点和与子树范围，或者换成适合区间查询的平衡树、线段树、树状数组。

七、加强记忆

BST 区间和的核心不是“会 DFS”，而是“会剪枝”：当前值小于下界时，左子树整片更小，砍掉左边；当前值大于上界时，右子树整片更大，砍掉右边；当前值落在闭区间内时，把当前值加入，并继续检查左右两边。回答时要特别强调边界包含、最坏 O(n)、递归栈 O(h)，这样既有代码，也有复杂度和剪枝依据。

简化版

详细版