th.jpg
102. 二叉树的层序遍历
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
使用队列实现二叉树广度优先遍历
var levelOrder = function(root) {
//二叉树的层序遍历
let res=[],queue=[];
queue.push(root);
if(root===null){
return res;
}
while(queue.length!==0){
// 记录当前层级节点数
let length=queue.length;
//存放每一层的节点
let curLevel=[];
while(length--){
let node=queue.shift();
curLevel.push(node.val);
// 存放当前层下一层的节点
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
}
//把每一层的结果放到结果数组
res.push(curLevel);
}
return res;
};
这是我们的万能公式，就是说接下来的好多题目，都是根据这个进行修改。
有的题目，甚至只需要修改一行代码，就可以 AC。
来看第一道
103. 二叉树的锯齿形层序遍历
这道题和之前那一道的差别就在于，放入的时候，偶数层的节点是倒叙的。那么可以想到，我们可以记录当前遍历的层数，当层数为偶数时，将当前存放节点的数组进行倒叙后放入。
var zigzagLevelOrder = function(root) {
//二叉树的层序遍历
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
let depth = 1;
while (queue.length !== 0) {
// 记录当前层级节点数
let length = queue.length;
depth++
//存放每一层的节点
let curLevel = [];
while (length--) {
let node = queue.shift();
curLevel.push(node.val);
// 存放当前层下一层的节点
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
//把每一层的结果放到结果数组
if (depth % 2 === 0) {
res.push(curLevel);
} else {
res.push(curLevel.reverse());
}
}
return res;
};
107. 二叉树的层序遍历 II
最后返回的结果，就是层序遍历的倒叙。那么我们只需要修改一行代码，即可 AC 本题。
ar levelOrderBottom = function(root) {
//二叉树的层序遍历
let res=[],queue=[];
queue.push(root);
if(root===null){
return res;
}
while(queue.length!==0){
// 记录当前层级节点数
let length=queue.length;
//存放每一层的节点
let curLevel=[];
for(let i=0;i<length;i++){
let node=queue.shift();
curLevel.push(node.val);
// 存放当前层下一层的节点
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
}
//把每一层的结果放到结果数组
res.push(curLevel);
}
return res.reverse();
};
111. 二叉树的最小深度
什么时候可以返回呢？就是当当前节点既没有左孩子也没有右孩子的时候。我们可以记录当前遍历的层数，当遇到第一个叶子结点的时候，停止遍历，返回层数。
var minDepth = function(root) {
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
let depth = 0
while (queue.length !== 0) {
// 记录当前层级节点数
let length = queue.length;
depth++;
while (length--) {
let node = queue.shift();
if (!node.left && !node.right) {
return depth
}
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
};
104. 二叉树的最大深度
使用变量，记录当前遍历的层数
var maxDepth = function(root) {
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
let depth = 0
while (queue.length !== 0) {
// 记录当前层级节点数
let length = queue.length;
depth++;
while (length--) {
let node = queue.shift();
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return depth
};
637. 二叉树的层平均值
这道题也是属于那种改一行代码就可以 AC 的那种。之前放入的是数组，那就数组的平均值，就很简单了。
var averageOfLevels = function(root) {
//二叉树的层序遍历
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
while (queue.length !== 0) {
// 记录当前层级节点数
let length = queue.length;
//存放每一层的节点
let curLevel = [];
while (length--) {
let node = queue.shift();
curLevel.push(node.val);
// 存放当前层下一层的节点
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
//把每一层的结果放到结果数组
res.push(curLevel.reduce((a, b) => a + b) / curLevel.length);
}
return res;
};
429. N 叉树的层序遍历
对于 N 叉树，则是对该节点的孩子结点进行遍历。
var levelOrder = function(root) {
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
while (queue.length !== 0) {
// 记录当前层级节点数
let length = queue.length;
//存放每一层的节点
let curLevel = [];
while (length--) {
let node = queue.shift();
curLevel.push(node.val);
// 存放当前层下一层的节点
for (let item of node.children) {
item && queue.push(item)
}
}
//把每一层的结果放到结果数组
res.push(curLevel);
}
return res;
};
199. 二叉树的右视图
当 length 不存在时，则就证明到达最后一个结点，此时即为右结点
var rightSideView = function(root) {
//二叉树的层序遍历
let res=[],queue=[];
queue.push(root);
if(root===null){
return res;
}
while(queue.length!==0){
// 记录当前层级节点数
let length=queue.length;
while(length--){
let node=queue.shift();
if(!length) {
res.push(node.val)
}
// 存放当前层下一层的节点
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
}
}
return res;
};
515. 在每个树行中找最大值
这道题也是属于改一行代码，就可以 AC 的。
var largestValues = function(root) {
//二叉树的层序遍历
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
while (queue.length !== 0) {
// 记录当前层级节点数
let length = queue.length;
//存放每一层的节点
let curLevel = [];
while (length--) {
let node = queue.shift();
curLevel.push(node.val);
// 存放当前层下一层的节点
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
//把每一层的结果放到结果数组
res.push(Math.max.apply(null, curLevel));
}
return res;
};
116. 填充每个节点的下一个右侧节点指针
var connect = function(root) {
if (root === null) return root;
let queue = [root];
while (queue.length) {
let length = queue.length;
for (let i = 0; i < length; i++) {
let node = queue.shift();
if (i < length - 1) {
node.next = queue[0];
}
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return root;
};
117. 填充每个节点的下一个右侧节点指针 II
var connect = function (root) {
if (root === null) return root;
let queue = [root];
while (queue.length) {
let length = queue.length;
for (let i = 0; i < length; i++) {
let node = queue.shift();
if (i < length - 1) {
node.next = queue[0];
}
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return root;
};
