1. 題目
2. 題解
# 938
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
# 方法1: 遞歸法
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
if root is None:
return 0
leftSum = self.rangeSumBST(root.left, low, high)
rightSum = self.rangeSumBST(root.right, low, high)
result = leftSum + rightSum
if low <= root.val <= high:
result += root.val
return result
# 方法2: BFS 寬度優先搜尋
def rangeSumBST_2(self, root: TreeNode, low: int, high: int) -> int:
result = 0
q = deque()
q.append(root)
while len(q) > 0:
size = len(q)
while size > 0:
cur = q.popleft()
if low <= cur.val <= high:
result += cur.val
if cur.left is not None:
q.append(cur.left)
if cur.right is not None:
q.append(cur.right)
size = size - 1
return