[LeetCode] 938. Range Sum of BST 二叉搜尋樹的區間和

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:

1. The number of nodes in the tree is at most 

   10000

   .
2. The final answer is guaranteed to be less than 

   2^31

這道題給了一棵二叉搜尋樹，還給了兩個整型數L和R，讓傳回所有結點值在區間 [L, R] 内的和，就是說找出所有的在此區間内的結點，将其所有結點值累加起來傳回即可。最簡單粗暴的思路就是周遊所有的結點，對每個結點值都檢測其是否在區間内，是的話就累加其值，最後傳回累加和即可，參見代碼如下：

解法一：

class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        int res = 0;
        helper(root, L, R, res);
        return res;
    }
    void helper(TreeNode* node, int L, int R, int& res) {
        if (!node) return;
        if (node->val >= L && node->val <= R) res += node->val;
        helper(node->left, L, R, res);
        helper(node->right, L, R, res);
    }
};
           

上面的解法雖然能過，但不是最優解，因為并沒有利用到二叉搜尋樹的性質，由于 BST 具有 左<根<右 的特點，是以就可以進行剪枝，若目前結點值小于L，則說明其左子樹所有結點均小于L，可以直接将左子樹剪去；同理，若目前結點值大于R，則說明其右子樹所有結點均大于R，可以直接将右子樹剪去。否則說明目前結點值正好在區間内，将其值累加上，并分别對左右子結點調用遞歸函數即可，參見代碼如下：

解法二：

class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        if (!root) return 0;
        if (root->val < L) return rangeSumBST(root->right, L, R);
        if (root->val > R) return rangeSumBST(root->left, L, R);
        return root->val + rangeSumBST(root->left, L, R) + rangeSumBST(root->right, L, R);
    }
};
           

Github 同步位址:

https://github.com/grandyang/leetcode/issues/938

參考資料：

https://leetcode.com/problems/range-sum-of-bst/

https://leetcode.com/problems/range-sum-of-bst/discuss/205181/Java-4-lines-Beats-100

https://leetcode.com/problems/range-sum-of-bst/discuss/192019/JavaPython-3-3-similar-recursive-and-1-iterative-methods-w-comment-and-analysis.

[LeetCode All in One 題目講解彙總(持續更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)

喜歡請點贊，疼愛請打賞❤️~.~

微信打賞

Venmo 打賞