Leetcode # 515. Find Largest Value in Each Tree Row

Problem

https://leetcode.com/problems/find-largest-value-in-each-tree-row

Solution: BFS

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

class Solution:
  def largestValues(self, root: Optional[TreeNode]) -> List[int]:
    if root is None: return []

    queue = deque([[root, 0]])
    lagest_value = {}
    while queue:
      node, level = queue.popleft()
      if level not in lagest_value:
        lagest_value[level] = -float("inf")
      lagest_value[level] = max(lagest_value[level], node.val)
      for child in [node.left, node.right]:
        if child is None: continue
        queue.append([child, level + 1])

    return [lagest_value[i] for i in range(max(lagest_value.keys()) + 1)]

Last Updated on 2024/12/25 by A1go