Problem:
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: L = 7, R = 15
10
/ \
5 15
/ \ \
3 7 18
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Example 2:
10
/ \
5 15
/ \ / \
3 7 13 18
/ /
1 6
Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23
Solution
If we can in-order traversal the BST, we can add the qualified the node values to the sum. The time cost is O(N), the space code is O(H), H is the tree height, which is equal to the height of the recursive call stack.
class Solution {
private int sum = 0;
private int L = 7;
private int R = 15;
public static void main(String[] args) {
Node root = new Node(10, new Node(5, new Node(3, null, null), new Node(7, null, null)), new Node(15, null, new Node(18, null, null)));
Solution slu = new Solution();
slu.solve(root);
System.out.println(slu.sum);
}
private void solve(Node root) {
if(root == null)
return;
if(root.val >= L && root.val <= R) {
sum += root.val;
}
if(root.val > R)
return; //no need to check further
solve(root.left);
solve(root.right);
}
private static class Node {
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
int val;
Node left;
Node right;
}
}
private int sum = 0;
private int L = 7;
private int R = 15;
public static void main(String[] args) {
Node root = new Node(10, new Node(5, new Node(3, null, null), new Node(7, null, null)), new Node(15, null, new Node(18, null, null)));
Solution slu = new Solution();
slu.solve(root);
System.out.println(slu.sum);
}
private void solve(Node root) {
if(root == null)
return;
if(root.val >= L && root.val <= R) {
sum += root.val;
}
if(root.val > R)
return; //no need to check further
solve(root.left);
solve(root.right);
}
private static class Node {
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
int val;
Node left;
Node right;
}
}
