DEV Community
·
515. 每层树行中的最大值
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定一棵二叉树的根节点，使用广度优先搜索（BFS）逐层遍历，返回每层的最大值数组。时间复杂度为O(n)，空间复杂度为O(w)，其中w为树的最大宽度。
🎯
关键要点
-
给定一棵二叉树的根节点，返回每层的最大值数组。
-
使用广度优先搜索（BFS）逐层遍历，适合查找每层的最大值。
-
需要处理空树和节点值范围内的边界情况。
-
使用BFS的基本步骤包括初始化队列和结果数组，逐层遍历树。
-
每层遍历时，记录最大值并将其添加到结果数组中。
-
时间复杂度为O(n)，空间复杂度为O(w)，其中w为树的最大宽度。
-
示例输入输出：输入为[1,3,2,5,3,null,9]，输出为[1,3,9]。
❓
延伸问答
如何在二叉树中找到每层的最大值？
可以使用广度优先搜索（BFS）逐层遍历二叉树，记录每层的最大值并返回结果数组。
广度优先搜索（BFS）在此问题中的作用是什么？
BFS适合逐层遍历二叉树，简化了每层最大值的查找过程。
该算法的时间复杂度和空间复杂度分别是多少？
时间复杂度为O(n)，空间复杂度为O(w)，其中w为树的最大宽度。
如何处理空树的情况？
如果根节点为null，则返回一个空数组。
能否使用深度优先搜索（DFS）解决这个问题？
可以，DFS也可以递归遍历树并记录每层的最大值，但BFS更适合逐层处理。
给定的示例输入输出是什么？
输入为[1,3,2,5,3,null,9]，输出为[1,3,9]。
➡️
