Problem
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
.
Solution: In-order traversal
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua, running time: 72 ms class Solution { public: int rangeSumBST(TreeNode* root, int L, int R) { if (!root) return 0; int sum = 0; if (root->val >= L) sum += rangeSumBST(root->left, L, R); if (root->val >= L && root->val <= R) sum += root->val; if (root->val <= R) sum += rangeSumBST(root->right, L, R); return sum; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment