给定一棵二叉树的根节点 root
,请找出该二叉树中每一层的最大值。
示例1:
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2:
输入: root = [1,2,3]
输出: [1,3]
二叉树的搜索无非就是DFS或者BFS,通常DFS用的比较多,这道题两个方法都可以,但是题目要求找到每一层的最大值,所以个人觉得层序遍历比较清晰,当然深度优先使用一个变量记录当前层数也可以完成这个任务。
DFS
递归遍历二叉树,每次进入下一层使层数加一,维护当前层数的最大值。
BFS
广度优先搜索,按模板写就行,在一层内维护一个最大值,遍历完一层后加入结果。
贴一个BFS:
class Solution {
public List largestValues(TreeNode root) {
if (root == null) {
return new ArrayList();
}
Deque queue = new LinkedList<>();
queue.offer(root);
List res = new ArrayList<>();
while (!queue.isEmpty()) {
int len = queue.size();
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
TreeNode node = queue.poll();
max = Math.max(max, node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(max);
}
return res;
}
}
原文:https://leetcode.cn/problems/find-largest-value-in-each-tree-row/solution/by-nice-hermann9a2-nnrq/
Original: https://www.cnblogs.com/liangren-na/p/16437673.html
Author: 良人呐
Title: 515. 在每个树行中找最大值
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/619843/
转载文章受原作者版权保护。转载请注明原作者出处!