-
Notifications
You must be signed in to change notification settings - Fork 0
/
range-sum-of-bst_938.py
52 lines (37 loc) · 1.35 KB
/
range-sum-of-bst_938.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 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].
# Example 1:
# 
# Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
# Output: 32
# Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.
# Example 2:
# 
# Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
# Output: 23
# Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.
# Constraints:
# The number of nodes in the tree is in the range [1, 2 * 104].
# 1 <= Node.val <= 105
# 1 <= low <= high <= 105
# All Node.val are unique.
# ---------------------------------------Runtime 132 ms Beats 88.16% Memory 24.4 MB Beats 97.94%---------------------------------------
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rangeSumBST(
self, root: Optional[TreeNode], low: int, high: int
) -> int:
res = 0
def dfs(node: TreeNode | None) -> None:
nonlocal res
if node:
if low <= node.val <= high:
res += node.val
dfs(node.left)
dfs(node.right)
dfs(root)
return res