Given the root
node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high]
.
Example 1:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 Output: 32
Example 2:
Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10 Output: 23
Constraints:
[1, 2 * 104]
.1 <= Node.val <= 105
1 <= low <= high <= 105
Node.val
are unique.Source
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def range_sum_bst(root, L, R):
"""DFS using a recursive approach"""
def dfs(node):
"""similar to preorder traversal"""
if not node:
return
nonlocal result
if L <= node.val <= R:
result += node.val
if node.val > L:
dfs(node.left)
if node.val < R:
dfs(node.right)
result = 0
dfs(root)
return result
Solve it both recursively and iteratively.
def range_sum_bst(root, L, R):
"""DFS using a recursive approach"""
if not root:
return 0
stack = [root]
result = 0
while stack:
node = stack.pop()
if node is None:
continue
if L <= node.val <= R:
result += node.val
if node.val > L:
stack.append(node.left)
if node.val < R:
stack.append(node.right)
return result
def range_sum_bst(root, L, R):
"""BFS using a recursive approach"""
if not root:
return 0
queue = [root]
result = 0
for node in queue:
if node is None:
continue
if L <= node.val <= R:
result += node.val
if node.val > L:
queue.append(node.left)
if node.val < R:
queue.append(node.right)
return result