写点什么

LeetCode 题解:515. 在每个树行中找最大值,BFS,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 12 月 10 日
LeetCode题解:515. 在每个树行中找最大值,BFS,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/



解题思路:



  1. 该题可以使用BFS,逐层遍历二叉树。

  2. 使用队列进行遍历,队列中按顺序存储了每一层的节点。

  3. 每次循环时,将队列中当前层的节点依次取出,即可在这次循环中,通过不断对比,获取到当前层的最大值。

  4. 同时,将当前层每个节点的子节点,依次存入队列尾部,等待下一次遍历处理。

  5. 不断重复步骤3、4,即可完成层序遍历,查找到每一行的最大值。



/**
* @param {TreeNode} root
* @return {number[]}
*/
var largestValues = function (root) {
let result = []; // 存储层序遍历结果
let queue = []; // 使用队列进行层序遍历,队列中存储的是每一层的所有节点
root && queue.push(root); // 如果树存在,才进行遍历
// 不断遍历队列,直到队列为空时,完成树的层序遍历
while (queue.length) {
// 缓存当前层的节点数量,避免队列操作过程中数量不断改变,对for循环次数造成影响
const queueLength = queue.length;
let max = -Infinity; // 存储当前层的最大值
// 当前层有多少个节点,就进行多少次循环取出节点
// 由于循环过程中,会不断向队列中入队下一层节点,因此queueLength必须固定
for (let i = 0; i < queueLength; i++) {
// 将当前层的节点依次从队列取出
const node = queue.shift();
// 不断地对比并存储当前层的最大值
max = Math.max(node.val, max);
// 如果子节点存在,则将子节点入队,作为下一层的节点
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
// 将当前层的最大值存入result
result.push(max);
}
return result;
};



发布于: 2020 年 12 月 10 日阅读数: 14
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:515. 在每个树行中找最大值,BFS,JavaScript,详细注释