938. 二叉搜索树的范围和
题目描述
输入一棵二叉搜索树的根节点 root，以及两个整数 low 和 high。树按层序用数组表示，null 表示空位。
找出所有值落在闭区间 [low, high] 内的节点，返回这些节点值的总和。
示例 1
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15 输出：32
解释：值在 [7,15] 内的节点是 7、10、15，和为 32。
示例 2
输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10 输出：23
解释：值在 [6,10] 内的节点是 6、7、10，和为 23。
数据范围
- 节点数在
[1, 2 * 10^4]范围内。 1 <= Node.val <= 10^51 <= low <= high <= 10^5- 各节点的值两两不同。
解题思路：递归剪枝搜索
利用 BST 性质剪枝：当前值小于 low，左子树更小，整个跳过，只搜右子树；大于 high，只搜左子树；在区间内，就把自己加上左右两边的结果。
为什么正确
rangeSumBST(x) 返回以 x 为根的子树中落在 [low, high] 内的值之和；被跳过的子树里不可能有区间内的值。
复杂度分析
时间 O(n)（最坏），剪枝后通常远少于 n；空间 O(h)。
易错点
剪枝方向别弄反：值太小时要去右边找更大的值；另外区间是闭区间，等于 low 或 high 的值也要算。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
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)class Solution {
public 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);
}
}class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if (root == nullptr) {
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);
}
};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)
}var rangeSumBST = function(root, low, 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);
};function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
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);
}其他解法
两种解法都用二叉搜索树性质剪枝；递归代码最短，广度优先搜索用显式队列避免递归深度问题。
解法 2：广度优先搜索 时间 O(n)，空间 O(n)
用队列从根节点开始逐个取出节点。节点值大于 high 时只入队左子节点，小于 low 时只入队右子节点。落在范围内时累加节点值，并把两个子节点都入队。
不使用递归，树很深时不会栈溢出。利用二叉搜索树性质的剪枝和主解法完全相同。
from collections import deque
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
total = 0
q = deque([root])
while q:
node = q.popleft()
if node is None:
continue
if node.val > high:
q.append(node.left)
elif node.val < low:
q.append(node.right)
else:
total += node.val
q.append(node.left)
q.append(node.right)
return totalclass Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
int total = 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node == null) continue;
if (node.val > high) {
q.offer(node.left);
} else if (node.val < low) {
q.offer(node.right);
} else {
total += node.val;
q.offer(node.left);
q.offer(node.right);
}
}
return total;
}
}class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
int total = 0;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node == nullptr) continue;
if (node->val > high) {
q.push(node->left);
} else if (node->val < low) {
q.push(node->right);
} else {
total += node->val;
q.push(node->left);
q.push(node->right);
}
}
return total;
}
};func rangeSumBST(root *TreeNode, low int, high int) int {
total := 0
q := []*TreeNode{root}
for len(q) > 0 {
node := q[0]
q = q[1:]
if node == nil {
continue
}
if node.Val > high {
q = append(q, node.Left)
} else if node.Val < low {
q = append(q, node.Right)
} else {
total += node.Val
q = append(q, node.Left, node.Right)
}
}
return total
}var rangeSumBST = function(root, low, high) {
let total = 0;
const q = [root];
for (let head = 0; head < q.length; head++) {
const node = q[head];
if (node === null) continue;
if (node.val > high) {
q.push(node.left);
} else if (node.val < low) {
q.push(node.right);
} else {
total += node.val;
q.push(node.left, node.right);
}
}
return total;
};function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
let total = 0;
const q: (TreeNode | null)[] = [root];
for (let head = 0; head < q.length; head++) {
const node = q[head];
if (node === null) continue;
if (node.val > high) {
q.push(node.left);
} else if (node.val < low) {
q.push(node.right);
} else {
total += node.val;
q.push(node.left, node.right);
}
}
return total;
}