Leetcode 515. Find Largest Value in Each Tree Row (Python)

Related Topic

Breadth-First-Search.

Description

You need to find the largest value in each row of a binary tree.

Sample I/O

Example 1

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

Methodology

Use BFS to traversal the tree level by level. Find the max value of each level and append to the res list. To traversal each level we need to know the size of each level and this is the key point.

Code(BFS)

def largestValues(self, root: TreeNode) -> List[int]:
        if not root: return []
        res = []
        queue = collections.deque([root])
        while queue:
            largest = -float('inf')
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.val > largest:
                    largest = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(largest)
        return res

BigO

We traversal all elements of the tree once so total time complexity is O(n)