Study NoteAppearance
二叉树的层序遍历
既递归遍历后，二叉树还有一种常用的遍历方法，就是层序遍历。
即逐层地，从左到右访问所有节点。
下面我们来学习下层序遍历的思路。
思路
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
需要借用一个辅助数据结构，即队列来实现。
队列先进先出的特性，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是广度优先遍历，只不过我们将用在图上的东西应用在了二叉树上。
开始刷题
二叉树的层序遍历
题目：102.二叉树的层序遍历
小 tips 🎗️：这个题算是层序遍历的模板题噢 ~ 务必牢记在心 ！！！
js
const ret = [];
if (!root) {
return ret;
}
const queue = [];
queue.push(root);
while (queue.length !== 0) {
ret.push([]);
let length = queue.length
for (let i = 1; i <= length; i++) {
const cur = queue.shift();
ret[ret.length - 1].push(cur.val);
if (cur.left){
queue.push(cur.left);
}
if (cur.right){
queue.push(cur.right);
}
}
}
return ret;
这道题跟上一题相比，就是将最终的结果进行了一个翻转，利用 reverse 即可，代码就不再重复了。
二叉树的右视图
题目：199.二叉树的右视图
相比于上文所述的层次遍历，右视图即相当于取到每一层的最右侧。
也就是一层数组中的最后一个元素。
思路：先进行层序遍历，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
js
var rightSideView = function(root) {
//二叉树右视图 只需要把每一层最后一个节点存储到res数组
let res = [], queue = [];
queue.push(root);
while(queue.length && root!==null) {
// 记录当前层级节点个数
let length = queue.length;
while(length--) {
let node = queue.shift();
// length长度为0的时候表明到了层级最后一个节点
if(!length) {
res.push(node.val);
}
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return res;
};
二叉树的层平均值
题目：637.二叉树的层平均值
求每一层的平均值。
跟右视图有点相似，一个是取当前层的最后一个，一个是取当前层的平均值。
js
var averageOfLevels = function(root) {
//层级平均值
let res = [], queue = [];
queue.push(root);
while(queue.length && root!==null) {
//每一层节点个数
let length = queue.length;
//sum记录每一层的和
let sum = 0;
for(let i=0; i < length; i++) {
let node = queue.shift();
sum += node.val;
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
//每一层的平均值存入数组res
res.push(sum/length);
}
return res;
};
N叉树的层序遍历
模板题 同 102.二叉树的层序遍历
js
var levelOrder = function(root) {
let queue = []
let res = []
queue.push(root)
while(queue.length && root !== null){
let curLev = []
let length = queue.length
while(length--) {
const node = queue.shift()
curLev.push(node.val)
for(i of node.children) {
i && queue.push(i)
}
}
res.push(curLev)
}
return res
};
在每个树行中找最大值
使用层序遍历模板，在每行中寻找最大值。
js
var largestValues = function(root) {
//使用层序遍历
let res = [], queue = [];
queue.push(root);
while(root !== null && queue.length) {
//设置max初始值就是队列的第一个元素
let max = queue[0].val;
let length = queue.length;
while(length--) {
let node = queue.shift();
max = max > node.val ? max : node.val;
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
//把每一层的最大值放到res数组
res.push(max);
}
return res;
};