leetcode 938. Range Sum of BST

Seawolf

1. Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).
   
2. 
   
3. The binary search tree is guaranteed to have unique values.
   
4. 
   
5. 
   
6. 
   
7. Example 1:
   
8. 
   
9. Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
   
10. Output: 32
    
11. Example 2:
    
12. 
    
13. Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
    
14. Output: 23
    
15. 
    
16. 
    
17. Note:
    
18. 
    
19. The number of nodes in the tree is at most 10000.
    
20. The final answer is guaranteed to be less than 2^31.

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public int rangeSumBST(TreeNode root, int L, int R) {
    
12.         if(root == null) return 0;
    
13.         return sum(root,L,R);
    
14.     }
    
15.    
    
16.     public int sum(TreeNode root, int L, int R){
    
17.         
    
18.         if(root == null) return 0;
    
19.         if(root.val >= L && root.val <= R) return root.val + sum(root.left,L,R) + sum(root.right,L,R);
    
20.         else if(root.val < L) return sum(root.right ,L,R);
    
21.         else return sum(root.left, L,R);
    
22.     }
    
23. }

复制代码