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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation