515. Find Largest Value in Each Tree Row

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

Example:

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

Solution

Approach 1: DFS.

Approach 2: BFS.

Code (Python)

Approach 1:

class Solution:
    def largestValues(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        result = []
        self._traverse(root, 0, result)
        return result
    
    def _traverse(self, node, level, result):
        if len(result) == level:
            result.append(node.val)
        result[level] = max(result[level], node.val)
        if node.left:
            self._traverse(node.left, level + 1, result)
        if node.right:
            self._traverse(node.right, level + 1, result)

Code (C++)

Approach 1:

Approach 2: