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.
Examples
Example1:
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15 Output: 32
Example2:
Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10 Output: 23
Our solution in 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) { //output variable int output = 0; // Create a stack Stack<TreeNode> stack = new Stack(); // Add the root node stack.push(root); // loop through each element while (!stack.isEmpty()) { // remove last item from stack TreeNode node = stack.pop(); // if the node exists if (node != null) { // incrememnt output counts if (L <= node.val && node.val <= R) output += node.val; // push if left if (L < node.val) stack.push(node.left); // push if right if (node.val < R) stack.push(node.right); } } // return our count return output; } }