- 题目描述
- 题解分析
- 解题代码
- 总结
题目描述
难度：中等
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
1
/
3 2
/
5 3 9
示例2：
输入: root = [1,2,3]
输出: [1,3]
解释:
1
/
2 3
示例3：
输入: root = [1] 输出: [1]
示例4：
输入: root = [1,null,2]
输出: [1,2]
解释:
1
2
示例5：
输入: root = [] 输出: []题解分析
二叉树每层的最大值，谈到每一层的访问就得提到二叉树的层序遍历了，利用层序遍历分别访问每一层的所有元素，然后利用 max 变量保存其中的最大值，这题也就迎刃而解；
层序遍历，顾名思义：按照一层层的逻辑遍历，一层遍历完了之后遍历下一层；
以下二叉树的层序遍历结果：1 , 3 , 2 , 5 , 3 , 9
1
/
3 2
/
5 3 9
那么如何完成层序遍历呢？
只需要利用到一个队列来保存每一层的所有元素，我们就可实现层序遍历了；
结合上面的二叉树，我们发现第一层只有一个节点，而它又有左右两个子节点，我们可以现将第一层的根节点 1 放入队列，随后弹出，然后将它的左子节点 3 与右子节点 2 分别入队，此时会发现第一层就已经访问结束了，并且队列中只剩下第二层的元素；
再次按照刚才的逻辑，将 3 弹出 并入队左子节点 5 与右子节点 3，再将 2 弹出 并入队右子节点 9 ，这样第二层也就访问完了，当前队列中又只剩下第三层的元素，如果一直持续这个逻辑，那么就可以按照一层一层的顺序访问完所有的元素；
那么我们保证队列不会弹出多余的元素，而是刚好弹出一层的元素呢？
我们可以利用变量 size 来记录每层元素的个数，当 size == 0 时，代表当前层已经遍历完了，要开始访问下一层了，并给 size 赋值为当前队列的元素个数，此时 size 就是下一层元素的个数了；( 每次 size 为 0 时，当前队列中的所有元素就为下一层的所有元素，可以仔细思考一下）
// 层序遍历
public List largestValues(TreeNode root) {
ArrayList values = new ArrayList<>();
if(root == null) return values;
ArrayDeque nodes = new ArrayDeque<>();
nodes.add(root); // 放入第一层
TreeNode node = null;
int max = root.val; // 保存每一层的最大值
int size = 1; // 记录每层的元素
while (!nodes.isEmpty()){
node = nodes.poll();
max = Math.max(max, node.val);
size--;
if(node.left != null){ // 左子节点入队
nodes.add(node.left);
}
if(node.right != null){ // 右子节点入队
nodes.add(node.right);
}
if(size == 0) { // 一层已经访问完了
values.add(max);
max = Integer.MIN_VALUE; // 重置 max
size = nodes.size(); // 重置size为下一层元素个数
}
}
return values;
}
总结
这题关键是需要理解二叉树的层序遍历，如果有同学不会或者忘了可以挑个时间搞一搞二叉树，这个东西面试爱问！再接再厉！
岁月悠悠，衰微只及肌肤；热忱抛却，颓废必致灵魂
