二叉搜索树（BST）的范围和查询（Range Sum Query）

问题描述
给定一个二叉搜索树（BST），每个节点包含一个整数值。需要实现一个功能，能够快速计算树中所有值在给定范围[low, high] 内的节点值之和。这个操作可能被多次调用，因此需要一个高效的算法。

BST 特性回顾
二叉搜索树的关键特性是：对于任意节点，其左子树的所有节点值都小于该节点值，其右子树的所有节点值都大于该节点值。这个特性使得我们可以高效地进行有序遍历。

基础解法：中序遍历累加

1. 思路：利用BST的中序遍历（左-根-右）会得到一个升序序列的特性。遍历整个树，当遇到节点值在[low, high]范围内时，累加其值。
2. 步骤：
   • 从根节点开始进行中序遍历（递归或迭代）。
   • 对于每个访问的节点：
     • 如果节点值小于low，由于BST特性，其左子树的所有节点值都更小，因此可以跳过左子树（实际上中序遍历自然处理，但这里指优化思路：若当前节点已小于low，则其左子树无需再判断，但中序遍历本身会先递归左子树，所以此优化在递归中需在遍历后判断，更佳方案见后续优化）。
     • 如果节点值在[low, high]内，将其值加入总和。
     • 如果节点值大于high，由于右子树所有节点值都更大，可以停止遍历（因为中序遍历是升序，后续节点值都会大于high）。
3. 时间复杂度：最坏情况下（如范围包含所有节点），需要遍历整个树，O(n)，其中n是节点数。每次查询都是O(n)。
4. 缺点：如果树很大且查询频繁，效率较低。

优化解法：利用BST特性剪枝

1. 思路：在中序遍历基础上，根据当前节点值与范围的关系，避免不必要的子树遍历。
2. 详细步骤（递归实现）：
   • 定义递归函数：rangeSumBST(node, low, high)，返回以node为根的子树中值在[low, high]范围内的节点值之和。
   • 基准情况：如果node为空，返回0。
   • 判断当前节点值（假设为val）：
     • 如果val < low：说明当前节点及其左子树的值都小于low，因此左子树和当前节点都不在范围内。只需递归计算右子树的范围和。
     • 如果val > high：说明当前节点及其右子树的值都大于high，因此右子树和当前节点都不在范围内。只需递归计算左子树的范围和。
     • 如果low <= val <= high：当前节点值在范围内，需要累加。同时，左子树中可能有部分节点值在范围内（虽然左子树值都小于val，但可能部分大于等于low），右子树同理（部分可能小于等于high）。因此需要递归计算左右子树的范围和，并加上当前节点值。
3. 时间复杂度：最优情况（范围很小或位于树边缘）可达到O(log n)，平均情况优于O(n)，因为剪枝避免了全树遍历。最坏情况（范围覆盖整棵树）仍是O(n)。
4. 代码示例（递归）：

   def rangeSumBST(root, low, high):
       if not root:
           return 0
       if root.val < low:
           # 当前节点值太小，只遍历右子树
           return rangeSumBST(root.right, low, high)
       elif root.val > high:
           # 当前节点值太大，只遍历左子树
           return rangeSumBST(root.left, low, high)
       else:
           # 当前节点在范围内，加上当前值并遍历左右子树
           return (root.val + 
                   rangeSumBST(root.left, low, high) + 
                   rangeSumBST(root.right, low, high))
   

进一步优化：迭代实现

1. 思路：使用栈模拟递归，避免递归函数调用开销，同时保持剪枝逻辑。
2. 步骤：
   • 初始化栈，将根节点压入栈，总和初始化为0。
   • 当栈非空时：
     • 弹出当前节点。
     • 如果节点为空，跳过。
     • 判断节点值：
       • 若val < low：仅将右子节点压栈（左子树肯定不在范围）。
       • 若val > high：仅将左子节点压栈（右子树肯定不在范围）。
       • 若val在范围内：将值加入总和，并将左右子节点都压栈（因为左右子树都可能存在范围内节点）。
   • 返回总和。
3. 代码示例（迭代）：

   def rangeSumBST(root, low, high):
       stack = [root]
       total = 0
       while stack:
           node = stack.pop()
           if not node:
               continue
           if node.val < low:
               stack.append(node.right)  # 只检查右子树
           elif node.val > high:
               stack.append(node.left)   # 只检查左子树
           else:
               total += node.val
               stack.append(node.left)   # 左右子树都需检查
               stack.append(node.right)
       return total
   

应用场景与扩展

• 实际应用：数据库索引范围查询、统计分数段学生人数等。
• 扩展思考：如果BST经常修改（插入/删除节点），如何支持高效的范围和查询？可结合线段树或树状数组（Fenwick Tree）的思想，但需维护额外信息（如子树和），并在更新时调整这些信息，实现O(log n)的查询和更新。

通过以上步骤，我们理解了BST范围和查询的基础解法、优化策略及实现方式，确保了算法的高效性。