[LeetCode] Problem 938 - Range Sum of BST

Posted on | In ,

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

No.1

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15

Output: 32

No.2

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10

Output: 23

Note

  1. The number of nodes in the tree is at most 10000.
  2. The final answer is guaranteed to be less than 2^31.

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private int sum = 0;

public int rangeSumBST(TreeNode root, int L, int R) {
    preorder(root, L, R);
    return sum;
}

private void preorder(TreeNode root, int L, int R) {
    if (root == null)
        return;

    if (root.val >= L && root.val <= R)
        sum += root.val;
    
    if (root.val > L)
        preorder(root.left, L, R);
    
    if (root.val < R)
        preorder(root.right, L, R);
}