(二叉树遍历)leetcode515. 在每个树行中找最大值-爱代码爱编程
一、题目
1、题目描述
给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。
示例1:
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2:
输入: root = [1,2,3]
输出: [1,3]
2、基础框架
- C++版本给出的基础框架如下:
3、原题链接
https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
二、解题报告
1、思路分析
(
1
)
(1)
(1)层序遍历,每次将队列一整层的节点取出,将其子节点放入队列中
(
2
)
(2)
(2)取出节点的时候记录该层的最大值
2、时间复杂度
时间复杂度为O(n),空间复杂度为O(n)
3、代码详解
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> re = new ArrayList<>();
if (root == null) return re;
LinkedList<TreeNode> que = new LinkedList<>();
que.add(root);
while(que.size() != 0) {
int n = que.size();
int max = 0;
for (int i=0; i < n; i++) {
TreeNode p = que.getFirst();
que.remove();
if (i == 0) max = p.val;
else max = Math.max(max, p.val);
if (p.left != null) {
que.add(p.left);
}
if (p.right != null) {
que.add(p.right);
}
}
re.add(max);
}
return re;
}
}
三、本题小知识
1.java队列知识,普通队列用LinkedList,优先队列使用PriorityQueue