938. 二叉搜索树的范围和

题目

给定二叉搜索树的根结点 root,返回 LR(含)之间的所有结点的值的和。

二叉搜索树保证具有唯一的值。

示例1:

1
2
输入:root = [10,5,15,3,7,null,18], low = 7, high = 15
输出:32

示例2:

1
2
输入:root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出:23

提示:

  1. 树中的结点数量最多为 10000 个。
  2. 最终的答案保证小于 2^31

解法

参考这里

解法一:

深度优先搜索-递归实现

我们对树进行深度优先搜索,对于当前节点 node,如果 node.val 小于等于 L,那么只需要继续搜索它的右子树;如果 node.val 大于等于 R,那么只需要继续搜索它的左子树;如果 node.val 在区间 (L, R) 中,则需要搜索它的所有子树。

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int rangeSumBST(TreeNode root, int L, int R) {
return dfs(root, L, R);
}

public int dfs(TreeNode node, int L, int R) {
int sum = 0;
if (node != null) {
if (L <= node.val && node.val <= R) {
sum += node.val;
}
if (L < node.val) {
sum += dfs(node.left, L, R);
}
if (node.val < R) {
sum += dfs(node.right, L, R);
}
}
return sum;
}

解法二:

深度优先搜索-迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int rangeSumBST(TreeNode root, int L, int R) {
int ans = 0;
Stack<TreeNode> stack = new Stack();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
if (L <= node.val && node.val <= R)
ans += node.val;
if (L < node.val)
stack.push(node.left);
if (node.val < R)
stack.push(node.right);
}
}
return ans;
}
0%