Open
Description
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:
- The number of nodes in the tree is at most
10000. - 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://leetcode.com/problems/range-sum-of-bst/
https://leetcode.com/problems/range-sum-of-bst/discuss/205181/Java-4-lines-Beats-100
Metadata
Metadata
Assignees
Labels
No labels