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]


## Solutions

### 1. BFS-两个指针的方式

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def largestValues(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
queue = [root]
last = n_last = root
res = []
level_max = float('-inf')
while queue:
node = queue.pop()
if node.val > level_max:
level_max = node.val
if node.left:
queue.insert(0, node.left)
n_last = node.left
if node.right:
queue.insert(0, node.right)
n_last = node.right
if node == last:
last = n_last
res.append(level_max)
level_max = float('-inf')
return res
# Runtime: 36 ms, faster than 75.28% of Python online submissions for Find Largest Value in Each Tree Row.
# Memory Usage: 16.2 MB, less than 33.33% of Python online submissions for Find Largest Value in Each Tree Row.


### 2. BFS-中序遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def largestValues(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
res = []
self.inorder(root, 0, res)
return res
def inorder(self, root, level, res):
if not root:
return
if len(res) <= level:
res.append(float('-inf'))
self.inorder(root.left, level+1, res)
if res[level] < root.val:
res[level] = root.val
self.inorder(root.right, level+1, res)

# Runtime: 40 ms, faster than 49.08% of Python online submissions for Find Largest Value in Each Tree Row.
# Memory Usage: 16.7 MB, less than 33.33% of Python online submissions for Find Largest Value in Each Tree Row.