Skip to content

Commit 6387d00

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problem: No.0938 (doocs#2376)
No.0938.Range Sum of BST
1 parent 0603c3f commit 6387d00

File tree

8 files changed

+400
-121
lines changed

8 files changed

+400
-121
lines changed

‎solution/0900-0999/0938.Range Sum of BST/README.md

Lines changed: 140 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,19 @@
3939

4040
## 解法
4141

42-
### 方法一
42+
### 方法一：DFS
43+
44+
我们设计一个函数 $dfs(root)$，表示求以 $root$ 为根的子树中，值位于范围 $[low, high]$ 之间的所有结点的值的和。那么答案就是 $dfs(root)$。
45+
46+
函数 $dfs(root)$ 的执行逻辑如下：
47+
48+
- 如果 $root$ 为空，返回 $0$。
49+
- 如果 $root$ 的值 $x$ 在范围 $[low, high]$ 之间，那么函数 $dfs(root)$ 的初始答案就是 $x$，否则为 $0$。
50+
- 如果 $x > low$，说明 $root$ 的左子树中可能有值在范围 $[low, high]$ 之间的结点，所以我们需要递归调用 $dfs(root.left)$，并将结果加到答案上。
51+
- 如果 $x < high$，说明 $root$ 的右子树中可能有值在范围 $[low, high]$ 之间的结点，所以我们需要递归调用 $dfs(root.right)$，并将结果加到答案上。
52+
- 最后返回答案。
53+
54+
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是二叉搜索树的结点个数。
4355

4456
<!-- tabs:start -->
4557

@@ -51,22 +63,19 @@
5163
# self.left = left
5264
# self.right = right
5365
class Solution:
54-
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
55-
def search(node):
56-
if not node:
57-
return
58-
if low <= node.val <= high:
59-
self.ans += node.val
60-
search(node.left)
61-
search(node.right)
62-
elif node.val < low:
63-
search(node.right)
64-
elif node.val > high:
65-
search(node.left)
66-
67-
self.ans = 0
68-
search(root)
69-
return self.ans
66+
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
67+
def dfs(root: Optional[TreeNode]) -> int:
68+
if root is None:
69+
return 0
70+
x = root.val
71+
ans = x if low <= x <= high else 0
72+
if x > low:
73+
ans += dfs(root.left)
74+
if x < high:
75+
ans += dfs(root.right)
76+
return ans
77+
78+
return dfs(root)
7079
```
7180

7281
```java
@@ -87,17 +96,22 @@ class Solution:
8796
*/
8897
class Solution {
8998
public int rangeSumBST(TreeNode root, int low, int high) {
99+
return dfs(root, low, high);
100+
}
101+
102+
private int dfs(TreeNode root, int low, int high) {
90103
if (root == null) {
91104
return 0;
92105
}
93-
if (low <= root.val && root.val <= high) {
94-
return root.val + rangeSumBST(root.left, low, high)
95-
+ rangeSumBST(root.right, low, high);
96-
} else if (root.val < low) {
97-
return rangeSumBST(root.right, low, high);
98-
} else {
99-
return rangeSumBST(root.left, low, high);
106+
int x = root.val;
107+
int ans = low <= x && x <= high ? x : 0;
108+
if (x > low) {
109+
ans += dfs(root.left, low, high);
110+
}
111+
if (x < high) {
112+
ans += dfs(root.right, low, high);
100113
}
114+
return ans;
101115
}
102116
}
103117
```
@@ -117,14 +131,21 @@ class Solution {
117131
class Solution {
118132
public:
119133
int rangeSumBST(TreeNode* root, int low, int high) {
120-
if (root == nullptr) return 0;
121-
if (low <= root->val && root->val <= high) {
122-
return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
123-
} else if (root->val < low) {
124-
return rangeSumBST(root->right, low, high);
125-
} else {
126-
return rangeSumBST(root->left, low, high);
127-
}
134+
function<int(TreeNode*)> dfs = [&](TreeNode* root) {
135+
if (!root) {
136+
return 0;
137+
}
138+
int x = root->val;
139+
int ans = low <= x && x <= high ? x : 0;
140+
if (x > low) {
141+
ans += dfs(root->left);
142+
}
143+
if (x < high) {
144+
ans += dfs(root->right);
145+
}
146+
return ans;
147+
};
148+
return dfs(root);
128149
}
129150
};
130151
```
@@ -139,16 +160,94 @@ public:
139160
* }
140161
*/
141162
func rangeSumBST(root *TreeNode, low int, high int) int {
142-
if root == nil {
143-
return 0
144-
}
145-
if low <= root.Val && root.Val <= high {
146-
return root.Val + rangeSumBST(root.Left, low, high) + rangeSumBST(root.Right, low, high)
147-
} else if root.Val < low {
148-
return rangeSumBST(root.Right, low, high)
149-
} else {
150-
return rangeSumBST(root.Left, low, high)
163+
var dfs func(*TreeNode) int
164+
dfs = func(root *TreeNode) (ans int) {
165+
if root == nil {
166+
return 0
167+
}
168+
x := root.Val
169+
if low <= x && x <= high {
170+
ans += x
171+
}
172+
if x > low {
173+
ans += dfs(root.Left)
174+
}
175+
if x < high {
176+
ans += dfs(root.Right)
177+
}
178+
return
151179
}
180+
return dfs(root)
181+
}
182+
```
183+
184+
```ts
185+
/**
186+
* Definition for a binary tree node.
187+
* class TreeNode {
188+
* val: number
189+
* left: TreeNode | null
190+
* right: TreeNode | null
191+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
192+
* this.val = (val===undefined ? 0 : val)
193+
* this.left = (left===undefined ? null : left)
194+
* this.right = (right===undefined ? null : right)
195+
* }
196+
* }
197+
*/
198+
199+
function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
200+
const dfs = (root: TreeNode | null): number => {
201+
if (!root) {
202+
return 0;
203+
}
204+
const { val, left, right } = root;
205+
let ans = low <= val && val <= high ? val : 0;
206+
if (val > low) {
207+
ans += dfs(left);
208+
}
209+
if (val < high) {
210+
ans += dfs(right);
211+
}
212+
return ans;
213+
};
214+
return dfs(root);
215+
}
216+
```
217+
218+
```cs
219+
/**
220+
* Definition for a binary tree node.
221+
* public class TreeNode {
222+
* public int val;
223+
* public TreeNode left;
224+
* public TreeNode right;
225+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
226+
* this.val = val;
227+
* this.left = left;
228+
* this.right = right;
229+
* }
230+
* }
231+
*/
232+
public class Solution {
233+
public int RangeSumBST(TreeNode root, int low, int high) {
234+
return dfs(root, low, high);
235+
}
236+
237+
private int dfs(TreeNode root, int low, int high) {
238+
if (root == null) {
239+
return 0;
240+
}
241+
int x = root.val;
242+
int ans = low <= x && x <= high ? x : 0;
243+
if (x > low) {
244+
ans += dfs(root.left, low, high);
245+
}
246+
if (x < high) {
247+
ans += dfs(root.right, low, high);
248+
}
249+
return ans;
250+
}
152251
}
153252
```
154253

0 commit comments

Comments
 (0)