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.