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
评论需要 JavaScript。