给定二叉搜索树的根结点 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 <= 105
1 <= low <= high <= 105
所有 Node.val 互不相同
方法一：深度优先搜索
思路
按深度优先搜索的顺序计算范围和。记当前子树根节点为 root，分以下四种情况讨论：
root 节点为空，返回 0。
root 节点的值大于high，由于二叉搜索树右子树上所有节点的值均大于根节点的值，即均大于high，故无需考虑右子树，返回左子树的范围和。
root 节点的值小于 low，由于二叉搜索树左子树上所有节点的值均小于根节点的值，即均小于 low，故无需考虑左子树，返回右子树的范围和。
root 节点的值在 [low, high] 范围内，此时应返回 root 节点的值、左子树的范围和、右子树的范围和这三者之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public 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);
}
}
|
复杂度分析
- 时间复杂度：O(n)，其中 n是二叉搜索树的节点数。
- 空间复杂度：O(n)。空间复杂度主要取决于栈空间的开销。
迭代写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public class Solution3 {
public int rangeSumBST(TreeNode root, int low, int high) {
int ans = 0;
Deque<TreeNode> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.addLast(root);
root = root.left;
}
root = stack.pollLast();
if (root.val > high) {
break;
}
if (root.val >= low) {
ans += root.val;
}
root = root.right;
}
return ans;
}
}
|
方法二：广度优先搜索
思路
使用广度优先搜索的方法，用一个队列 q 存储需要计算的节点。每次取出队首节点时，若节点为空则跳过该节点，否则按方法一中给出的大小关系来决定加入队列的子节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class Solution2 {
public int rangeSumBST(TreeNode root, int low, int high) {
int ans = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
continue;
}
if (node.val > high) {
queue.offer(node.left);
} else if (node.val < low) {
queue.offer(node.right);
} else {
ans += node.val;
queue.offer(node.left);
queue.offer(node.right);
}
}
return ans;
}
}
|
复杂度分析
- 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。
- 空间复杂度：O(n)。空间复杂度主要取决于队列的空间。