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]

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if not root:
             return [] 
         q = [root]
         r = []
         while q:
             r.append(max([i.val for i in q]))
             q = [i for node in q for i in [node.left, node.right] if i]
         return r

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if not root:
             return []
         res = []
         queue = []
         queue.append(root)
         while queue:
             length = len(queue)
             res.append(max([i.val for i in queue]))
             for i in range(length):
                 node = queue.pop(0)
                 if node.left:
                     queue.append(node.left)
                 if node.right:
                     queue.append(node.right)
         return res

from collections import deque
 
 class Solution:
     def largestValues(self, root):
         if root is None: return []
         q = deque([(root, 0)])
         l = [root.val]
         # l contains the largest values in each level from 0 to len(l) - 1
         while len(q) != 0:
             (node, level) = q.pop()
             if level == len(l) - 1:
                 l[-1] = max(l[-1], node.val)
             else:
                 l.append(node.val)
             if node.left:
                 q.appendleft((node.left, level + 1))
             if node.right:
                 q.appendleft((node.right, level + 1))
         
         return l

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         ret = []
         row = []
         next_row = []
 
         if root:
             next_row.append(root) 
 
         while next_row:
             current_max = None
             row = next_row
             next_row = []
             for node in row:
                 if current_max == None or current_max < node.val:
                     current_max = node.val
                 if node.left:
                     next_row.append(node.left) 
                 if node.right:
                     next_row.append(node.right) 
             ret.append(current_max)
 
         return ret

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         ret = []
         row = []
         next_row = []
 
         if root:
             next_row.append(root) 
 
         while next_row:
             current_max = None
             row = next_row
             next_row = []
             for node in row:
                 if current_max == None or current_max < node.val:
                     current_max = node.val
                 if node.left:
                     next_row.append(node.left) 
                 if node.right:
                     next_row.append(node.right) 
             ret.append(current_max)
 
         return ret

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def bfs(self, root):
         queue = [root]
         result = []
         while queue:
             next_q = []
             max_val = -float("inf")
             for node in queue:
                 max_val = max(max_val, node.val)
                 if node.left:
                     next_q.append(node.left)
                 if node.right:
                     next_q.append(node.right)
             result.append(max_val)
             queue = next_q
         return result
         
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         return self.bfs(root) if root else []
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         result=[]
         if root==None:
             return result
         queue=[root]
         curr_row_values=[]
         next_queue=[]
         while len(queue)>0:
             node=queue.pop()
             
             if node!=None:
                 curr_row_values.append(node.val)
                 next_queue.append(node.left)
                 next_queue.append(node.right)
             if len(queue)==0 and len(next_queue)>0:
                 result.append(max(curr_row_values))
                 curr_row_values=[]
                 queue=next_queue
                 next_queue=[]
         return result

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         level = []
         if root == None:
             return []
         level.append(root)
         ans = []
         
         while len(level) != 0:
             level_max = float("-inf")
             next_level = []
             while len(level) != 0:
                 cur_node = level.pop(0)
                 level_max = max(cur_node.val, level_max)
                 if cur_node.left != None:
                     next_level.append(cur_node.left)
                 if cur_node.right != None:
                     next_level.append(cur_node.right)
             ans.append(level_max)
             level = next_level
         return ans
         
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if not root:
             return []
         
         queue = [root]
         ans = []
         
         while queue:
             temp = -float("inf")
             size = len(queue)            
             for i in range(size):
                 node = queue.pop(0)
                 temp = max(temp, node.val)
                 if node.left:
                     queue.append(node.left)
                 if node.right:
                     queue.append(node.right)
             ans.append(temp)
             
         return ans
                 
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if not root:
             return []
         stack = []
         finallist = [root.val]
         if root.left:
             stack.append(root.left)
         if root.right:
             stack.append(root.right)
         
 
         while stack:
             #print(stack)
             temp = []
             maxval =-2147483648
             for node in stack:
                 #node = stack.pop()
                 maxval = max(maxval,node.val)
                 if node.right:
                     temp.append(node.right)
                 if node.left:
                     temp.append(node.left)
             
             finallist.append(maxval)
             stack = temp
             
         return finallist
                 
         
             
         
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if root is None:
             return []
         r = []
         s = [root]
         t = []
         while True:
             mx = float('-inf')
             for x in s:
                 if x.left != None:
                     t.append(x.left)
                 if x.right != None:
                     t.append(x.right)
                 if x.val > mx:
                     mx = x.val
             r.append(mx)
             if len(t)>0:
                 s=t
                 t=[]
             else:
                 return r

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if root==None:
             return []
         if root.left==None and root.right==None:
             return [root.val]
         if root.left:
             l = self.largestValues(root.left)
         else:
             l = []
         if root.right:
             r = self.largestValues(root.right)
         else:
             r = []
         out = [root.val]
         for i in range(min(len(l),len(r))):
             out.append(max(l[i],r[i]))
         if len(l)<len(r):
             out = out + r[len(l):]
         elif len(r)<len(l):
             out = out + l[len(r):]
         return out
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def largestValues(self, root):
         """
         :type root: TreeNode
         :rtype: List[int]
         """
         if(root == None):
             return []
         rowmax = []
         self.findRowMax(root, 1, rowmax)
         return rowmax
         
         
     def findRowMax(self, root, level, rowmax):
         if(level > len(rowmax)):
             rowmax.append(root.val)
         else:
             if(root.val > rowmax[level-1]):
                 rowmax[level-1] = root.val
         if(root.left != None):
             self.findRowMax(root.left, level+1, rowmax)
         if(root.right != None):
             self.findRowMax(root.right, level+1, rowmax)