# Question

Formatted question description: https://leetcode.ca/all/938.html

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

Example 2:

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

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



# Algorithm 1

This question gives a binary search tree, and also gives two integers L and R, so that the sum of all node values in the interval [L, R] is returned, that is, to find all the values in this interval For the nodes within, add up all the node values and return. The simplest and rude idea is to traverse all the nodes, check whether the value of each node is in the interval, if it is, add its value, and finally return the accumulated sum, see the code as follows:

C++

Java

# Algorithm 2

Although the above solution can be passed, it is not the optimal solution, because the nature of the binary search tree is not used. Since BST has the characteristics of left< root< right, pruning can be carried out, if the current node value is less than L , It means that all nodes of the left subtree are less than L, and the left subtree can be cut directly; similarly, if the current node value is greater than R, it means that all nodes of the right subtree are greater than R, and you can directly Cut the right subtree. Otherwise, it means that the current node value is exactly in the interval, add up its value, and call the recursive function on the left and right sub-nodes respectively, see the code as follows:

# Code 2

C++

Java

/**
* 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) {
List<Integer> inorderTraversal = inorderTraversal(root);
int leftIndex = inorderTraversal.indexOf(L), rightIndex = inorderTraversal.indexOf(R);
int sum = 0;
for (int i = leftIndex; i <= rightIndex; i++)
sum += inorderTraversal.get(i);
return sum;
}

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> inorderTraversal = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
TreeNode visitNode = stack.pop();