515. Find Largest Value in Each Tree Row

Problem

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

https://leetcode.com/problems/find-largest-value-in-each-tree-row/

Example 1:

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

Example 2:

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

Constraints:

The number of nodes in the tree will be in the range [0, 10⁴].
-2³¹ <= Node.val <= 2³¹ - 1

Test Cases

# 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: Optional[TreeNode]) -> List[int]:

solution_test.py

import pytest

import os
import sys
sys.path.append(os.path.dirname(os.path.dirname(__file__)))
from _utils.binary_tree import build_tree
from solution import Solution

null = None


@pytest.mark.parametrize('root, expected', [
    ([1,3,2,5,3,null,9], [1,3,9]),
    ([1,2,3], [1,3]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, root, expected):
    assert sol.largestValues(build_tree(root)) == expected

Thoughts

直接像 2471. Minimum Number of Operations to Sort a Binary Tree by Level 一样逐层遍历（层序遍历）二叉树，记录每层的最大值即可。

Code

solution.py

from typing import Optional


# 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: Optional[TreeNode]) -> list[int]:
        if not root: return []

        answer = []
        row = [root]
        while row:
            answer.append(max(node.val for node in row))
            row = [c for node in row for c in (node.left, node.right) if c]

        return answer