[LeetCode] Range Sum of BST

938. 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].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
int dnc(TreeNode* root, int mi, int ma, int l, int h) {
if(!root) return 0;
if(ma < l or mi > h) return 0;
int res = 0;
if(l <= root->val and root->val <= h) res += root->val;
return res + dnc(root->left, mi, root->val, l, h) + dnc(root->right, root->val, ma, l, h);
}
public:
int rangeSumBST(TreeNode* root, int low, int high) {
return dnc(root, INT_MIN, INT_MAX, low, high);
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/12/07/PS/LeetCode/range-sum-of-bst/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.