LeetCode | 0515. 在每个树行中找最大值【Python】

柔情只为你懂 2023-01-09 03:57 130阅读 0赞

## Problem ##

[LeetCode][]

Given the `root` of a binary tree, return *an array of the largest value in each row* of the tree **(0-indexed)**.

**Example 1:**

![img][]

Input: root = [1,3,2,5,3,null,9]
    Output: [1,3,9]

**Example 2:**

Input: root = [1,2,3]
    Output: [1,3]

**Example 3:**

Input: root = [1]
    Output: [1]

**Example 4:**

Input: root = [1,null,2]
    Output: [1,2]

**Example 5:**

Input: root = []
    Output: []

**Constraints:**

*  The number of nodes in the tree will be in the range `[0, 104]`.
 *  `-231 <= Node.val <= 231 - 1`

## 问题 ##

[力扣][Link 1]

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

**示例：**

输入: 
    	  1
         / \
        3   2
       / \   \  
      5   3   9 
    输出: [1, 3, 9]

## 思路 ##

**BFS**

使用 BFS 遍历完每一层，将该层最大值加入 res 中。

### Python3 代码 ###

# 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]:
            import collections
            if not root:
                return []
            res = []
            q = collections.deque()
            q.append(root)
            while q:
                size = len(q)
                tmp_max = -float('inf')
                # 取每一层最大值
                for i in range(size):
                    node = q.popleft()
                    tmp_max = max(tmp_max, node.val)
                    # 一层树遍历完，加入该层最大值
                    if i == size - 1:
                        res.append(tmp_max)
                    if node.left:
                        q.append(node.left)
                    if node.right:
                        q.append(node.right)
            return res

## GitHub 链接 ##

[Python][]

[LeetCode]: https://leetcode.com/problems/find-largest-value-in-each-tree-row/
[img]: /images/20221119/60e363ce43814811b07738fbd5ad2058.png
[Link 1]: https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
[Python]: https://github.com/Wonz5130/LeetCode-Solutions/blob/master/solutions/0515-Find-Largest-Value-in-Each-Tree-Row/0515.py