题解:
二叉树中序遍历, 递加在 [L , R] 范围的元素即可。
思路一:
递归 代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
|
int sum = 0;
public int rangeSumBST(TreeNode root, int L, int R){
if (root == null) return 0;
rangeSumBST(root.left, L ,R);
if (root.val >= L && root.val <= R){
sum += root.val;
}
rangeSumBST(root.right,L,R);
return sum;
}
|
思路二:
迭代 代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// 迭代
public int rangeSumBST1(TreeNode root, int L, int R){
if (root == null) return 0;
// 保存最终结果
int sum = 0;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null){
while (root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.val >= L && root.val <= R){
sum += root.val;
}
root = root.right;
}
return sum;
}
|