Given the
root
node of a binary search tree, return the sum of values of all nodes with value between
L
and
R
(inclusive).
The binary search tree is guaranteed to have unique values.
Example 1:
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
思路:Divide and conquer
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rangeSumBST(TreeNode root, int L, int R) {
if(root == null) {
return 0;
}
int sum = 0;
sum += rangeSumBST(root.left, L, R);
sum += rangeSumBST(root.right, L, R);
if(L <= root.val && root.val <= R) {
sum += root.val;
}
return sum;
}
}