Leetcode # 938. Range Sum of BST

https://leetcode.com/problems/range-sum-of-bst/

Solution

Time Complexity: O(len(tree))
Space Complexity: O(len(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
    queue = collections.deque([root])
    sum = 0
    while queue:
      cur = queue.popleft()
      if not cur: continue
      if cur.val < low:
        queue.append(cur.right)
      elif cur.val > high:
        queue.append(cur.left)
      else:
        queue.append(cur.left)
        queue.append(cur.right)
        sum += cur.val
    return sum

Last Updated on 2023/08/16 by A1go