Although this is an easy question, but it is prone to bugs, and the code can be better.
Following is my first solution, didn't use the feature of BST.
private int sum =0; public int rangeSumBST(TreeNode root, int low, int high) { if(root==null) return sum; if(root.val>=low&&root.val<=high){ sum+=root.val; } rangeSumBST(root.left, low, high); //whether root.val is in the range or not, this line should be executed, think about why rangeSumBST(root.right, low, high); //whether root.val is in the range or not, this line should be executed, think about why
return sum; }
The following solution use the feature of BST, reduced unnecessary implementations:
private int sum =0; public int rangeSumBST(TreeNode root, int low, int high) { if(root==null) return sum; if(root.val>high) rangeSumBST(root.left, low, high); else if(root.val<low) rangeSumBST(root.right, low, high); else{ sum+=root.val; rangeSumBST(root.left, low, high); rangeSumBST(root.right, low, high); } return sum; }
The sum in above solution can be removed:
public int rangeSumBST(TreeNode root, int low, int high) { if (root == null) return 0; if (root.val > high) return rangeSumBST(root.left, low, high); else if (root.val < low) return rangeSumBST(root.right, low, high); else { return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) + root.val; } }