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

Example:

1
2
3
4
5
6
7
8
9
Input: 
          1
         / \
        3   2
       / \   \  
      5   3   9 
Output: [1, 3, 9]

思路

这一题可以简单地采用层次遍历的方法。在层次遍历的队列当中加入空元素的方法，来分隔每一层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import Queue
class Solution(object):
    def largestValues(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        q = Queue.Queue()
        ans = []
        stats = []
        if (root):
            q.put(root)
            q.put(None)
            while not q.empty():
                cur = q.get()
                if (cur):
                    stats.append(cur.val)
                    if (cur.left):
                        q.put(cur.left)
                    if (cur.right):
                        q.put(cur.right)
                else:
                    if (q.empty()):
                        if (stats):
                            ans.append(max(stats))
                        break
                    else:
                        if (stats):
                            ans.append(max(stats))
                        stats = []
                        q.put(None)
        return ans

这个解法就比较厉害了：https://discuss.leetcode.com/topic/78991/python-bfs/3