Leetcode 515.在每个树行中找最大值

Posted on |

515.在每个树中找最大值

题目

您需要在二叉树的每一行中找到最大的值。

1
2
3
4
5
6
7
8
9
10
11
示例：

输入:

          1
         / \
        3   2
       / \   \  
      5   3   9

输出: [1, 3, 9]

方法

方法1：宽度优先遍历

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
# 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=collections.deque([(root)])
        ans=[]
        while queue:
            level=[]
            for i in range(len(queue)):
                node=queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                level.append(node.val)
            ans.append(max(level))
        return ans
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
# 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]
        """
        ans = []
        if not root:
            return ans
        node = [root]
        while node:
            ans.append(max([i.val for i in node]))
            curr = []
            for each in node:
                if each.left:
                    curr.append(each.left)
                if each.right:
                    curr.append(each.right)
                node = curr
        return ans
`