LeetCode - Easy - 938. Range Sum of BST

末蓝、 2022-10-16 06:14 56阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Recursion

## Description ##

[https://leetcode.com/problems/range-sum-of-bst/][https_leetcode.com_problems_range-sum-of-bst]

Given the `root` node of a binary search tree and two integers `low` and `high`, return the sum of values of all nodes with a value in the **inclusive** range `[low, high]`.

**Example 1:**

![e9cfb8823e63c14cda30772a6f3efbbe.png][]

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
    Output: 32
    Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

**Example 2:**

![fdf65f2fc11298bf85ee17480bce1f88.png][]

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
    Output: 23
    Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 1 , 2 ∗ 1 0 4 \] \[1, 2 \* 10^4\] \[1,2∗104\].
 *   1 < = N o d e . v a l < = 1 0 5 1 <= Node.val <= 10^5 1<=Node.val<=105
 *   1 < = l o w < = h i g h < = 1 0 5 1 <= low <= high <= 10^5 1<=low<=high<=105
 *  All `Node.val` are **unique**.

## Analysis ##

方法一：遍历所有节点，符合范围的值进行累加。本法未利用BST有序特性。

方法二：利用BST有序特性的递归法。

方法三：利用BST有序特性的迭代法。

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class RangeSumOfBST { 
    	
    	//方法一：遍历所有节点，符合要求进行累加
        public int rangeSumBST(TreeNode root, int low, int high) { 
            int[] sum = { 0};
        	inorderTraverse(root, low, high, sum);
        	return sum[0];
        }
        
        private void inorderTraverse(TreeNode node, int low, int high, int[] sum) { 
        	if(node == null) 
        		return;
        	
        	inorderTraverse(node.left, low, high, sum);
        	
        	if(low <= node.val && node.val <= high)
        		sum[0] += node.val;
        	
        	inorderTraverse(node.right, low, high, sum);
        }
        
        //方法二：递归版
        public int rangeSumBST2(TreeNode root, int L, int R) { 
            if (root == null) return 0; // base case.
            if (root.val < L) return rangeSumBST(root.right, L, R); // left branch excluded.
            if (root.val > R) return rangeSumBST(root.left, L, R); // right branch excluded.
            //剩下的就是 L <= root.val && root.val <= R
            return root.val + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R); // count in both children.
        }
        
        //方法三：迭代法
        public int rangeSumBST3(TreeNode root, int L, int R) { 
            LinkedList<TreeNode> stk = new LinkedList<>();
            stk.push(root);
            int sum = 0;
            while (!stk.isEmpty()) { 
                TreeNode n = stk.pop();
                if (n == null) {  continue; }
                if (n.val > L) {  stk.push(n.left); } // left child is a possible candidate.
                if (n.val < R) {  stk.push(n.right); } // right child is a possible candidate.
                if (L <= n.val && n.val <= R) {  sum += n.val; }
            }
            return sum;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class RangeSumOfBSTTest { 
    
    	@Test
    	public void test() { 
    		RangeSumOfBST obj = new RangeSumOfBST();
    		
    		TreeNode root1 = BinaryTree.integers2BinaryTree(10, 5, 15, 3, 7, null, 18);
    		assertEquals(32, obj.rangeSumBST(root1, 7, 15));
    		assertEquals(32, obj.rangeSumBST2(root1, 7, 15));
    		assertEquals(32, obj.rangeSumBST3(root1, 7, 15));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(10, 5, 15, 3, 7, 13, 18, 1, null, 6);
    		assertEquals(23, obj.rangeSumBST(root2, 6, 10));
    		assertEquals(23, obj.rangeSumBST2(root2, 6, 10));
    		assertEquals(23, obj.rangeSumBST3(root2, 6, 10));
    	}
    }

[https_leetcode.com_problems_range-sum-of-bst]: https://leetcode.com/problems/range-sum-of-bst/
[e9cfb8823e63c14cda30772a6f3efbbe.png]: /images/20221014/0037e336204b45c68797843e63dd8672.png
[fdf65f2fc11298bf85ee17480bce1f88.png]: /images/20221014/4937602cda6a4277a32c7227450a0b95.png