广度优先遍历 BFS
解题思路
对二叉树进行层次遍历；
每一层遍历时，找出当前层的最大值，放入 res 中；
重复上述操作直到队列为空，遍历结束；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树节点个数，每一个节点仅会进出队列一次； -
空间复杂度：
O(n)，存储二叉树节点的空间开销；
代码实现
var largestValues = function (root) {
if (root === null) return [];
let res = [];
let queue = [root];
while (queue.length) {
let len = queue.length;
let maxNum = -Infinity;
while (len--) {
let node = queue.shift();
maxNum = Math.max(maxNum, node.val);
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
res.push(maxNum);
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 637. 二叉树的层平均值
上一篇
评论
