@[TOC]([LeetCode解题报告] 515. 在每个树行中找最大值 )

一、 题目1. 题目描述1. 在每个树行中找最大值

难度：中等

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]输出: [1,3,9]

示例2：

输入: root = [1,2,3]输出: [1,3]

提示：

• 二叉树的节点个数的范围是 [0,104]• -231 <= Node.val <= 231 - 12. 原题链接

链接: 515. 在每个树行中找最大值

二、 解题报告1. 思路分析• 今天的题目十分简单，对二叉树进行层序遍历即可。• 咱们用的是python，因此在每层创建新的队列，记录一个最大值，最后添加进ans就可以了。• 啪的一下，cv很快啊。2. 复杂度分析

最坏时间复杂度*O(n)*，n是树上节点数量。

3. 代码实现

层序遍历。

class Solution:    def largestValues(self, root: Optional[TreeNode]) -> List[int]:        if not root :            return []        ans = []        q = deque([root])        while q:            new_q = deque()            m = -1e13            while q:                root = q.popleft()                m = max(m,root.val)                if root.left:                    new_q.append(root.left)                if root.right:                    new_q.append(root.right)            q = new_q            ans.append(m)        return ans