二叉树每层的最大值
# 📃 题目描述
题目链接:
- 剑指 Offer II 044. 二叉树每层的最大值 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 515. 在每个树行中找最大值 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。
示例1:
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
1
/ \
3 2
/ \ \
5 3 9
# 🔔 解题思路
层序遍历,使用一个变量记录每层的最大值即可
class Solution {
public List<Integer> largestValues(TreeNode root) {
// 记录每一层的最大值
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
// 存储当前层的最大值
int maxVal = Integer.MIN_VALUE;
// 遍历当前层
for (int i = 0; i < size; i ++) {
TreeNode cur = queue.poll();
maxVal = Math.max(maxVal, cur.val);
// 左右孩子入队
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
res.add(maxVal);
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10