难度: Easy
给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
示例 1：
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15 输出：32
示例 2：
输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10 输出：23
提示：
[1, 2 * 104] 内1 <= Node.val <= 1051 <= low <= high <= 105Node.val 互不相同运行时间: 180 ms
内存: 23.6 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
s = 0
if root is None:
return s
if root.val < low:
return self.rangeSumBST(root.right, low, high)
if root.val > high:
return self.rangeSumBST(root.left, low, high)
s += root.val
s += self.rangeSumBST(root.left, low, high)
s += self.rangeSumBST(root.right, low, high)
return s
此题解采用递归方法解决二叉搜索树中的范围求和问题。首先，检查当前节点是否为空，若为空，则返回和为0。其次，根据二叉搜索树的性质，如果当前节点的值小于下限low，则只需递归右子树；如果当前节点的值大于上限high，则只需递归左子树。如果当前节点的值在[low, high]范围内，则将其值加到总和中，并继续递归左右子树。这种方法有效利用了二叉搜索树的性质，减少了不必要的节点访问。
时间复杂度: O(n)
空间复杂度: O(h)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
if root is None: # 检查当前节点是否为空
return 0
if root.val < low: # 当前节点值小于下限，只递归右子树
return self.rangeSumBST(root.right, low, high)
if root.val > high: # 当前节点值大于上限，只递归左子树
return self.rangeSumBST(root.left, low, high)
# 当前节点值在范围内，计算总和并递归左右子树
return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
在二叉搜索树中，任何一个节点的左子节点的值都小于该节点的值。因此，如果当前节点的值已经小于下限low，那么其左子树中的所有节点的值也必然小于low。这意味着左子树中的所有节点的值都不会在[low, high]的范围内，所以递归左子树不会对结果产生贡献，不需要检查左子树。
在递归过程中，每个节点只会被访问一次。当一个节点的值在[low, high]范围内时，其值被加入到总和中，并且递归地访问该节点的左子树和右子树。由于二叉搜索树的性质保证了每个节点的值都是独一无二的，并且在递归中每个节点只处理一次，因此不会出现重复计算节点值的问题。
在题解中，当节点值位于包括low和high在内的[low, high]区间时，都将节点值加入总和，并继续递归访问左右子树。因此，节点值正好等于low或high时，处理逻辑与其节点值位于low和high之间时相同，即包括这些值在内进行总和计算，并继续递归访问其左右子树。
为了优化当low和high非常接近时的查询效率，可以在遍历树的过程中更加精确地定位到包含low和high的区域。具体来说，可以修改算法，在遍历到一个节点时，首先判断该节点值是否在[low, high]范围内：如果当前节点值小于low，直接递归右子树；如果当前节点值大于high，直接递归左子树；如果当前节点值在范围内，则加入总和并递归左右子树。此外，还可以利用迭代而非递归的方式，使用栈来模拟递归过程，减少递归调用的开销，并能够在找到范围内的节点后快速终止其他不必要的搜索，从而提高效率。