th.jpg
102. 二叉樹的層序遍歷
層序遍歷一個(gè)二叉樹帆疟。就是從左到右一層一層的去遍歷二叉樹辫樱。
需要借用一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)即隊(duì)列來實(shí)現(xiàn)，隊(duì)列先進(jìn)先出，符合一層一層遍歷的邏輯锻煌，而是用棧先進(jìn)后出適合模擬深度優(yōu)先遍歷也就是遞歸的邏輯谷丸。
而這種層序遍歷方式就是圖論中的廣度優(yōu)先遍歷，只不過我們應(yīng)用在二叉樹上购城。
使用隊(duì)列實(shí)現(xiàn)二叉樹廣度優(yōu)先遍歷
var levelOrder = function(root) {
//二叉樹的層序遍歷
let res=[],queue=[];
queue.push(root);
if(root===null){
return res;
}
while(queue.length!==0){
// 記錄當(dāng)前層級(jí)節(jié)點(diǎn)數(shù)
let length=queue.length;
//存放每一層的節(jié)點(diǎn)
let curLevel=[];
while(length--){
let node=queue.shift();
curLevel.push(node.val);
// 存放當(dāng)前層下一層的節(jié)點(diǎn)
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
}
//把每一層的結(jié)果放到結(jié)果數(shù)組
res.push(curLevel);
}
return res;
};
這是我們的萬能公式吕座，就是說接下來的好多題目，都是根據(jù)這個(gè)進(jìn)行修改瘪板。
有的題目吴趴，甚至只需要修改一行代碼，就可以 AC侮攀。
來看第一道
103. 二叉樹的鋸齒形層序遍歷
這道題和之前那一道的差別就在于锣枝，放入的時(shí)候，偶數(shù)層的節(jié)點(diǎn)是倒敘的兰英。那么可以想到撇叁，我們可以記錄當(dāng)前遍歷的層數(shù)，當(dāng)層數(shù)為偶數(shù)時(shí)畦贸，將當(dāng)前存放節(jié)點(diǎn)的數(shù)組進(jìn)行倒敘后放入陨闹。
var zigzagLevelOrder = function(root) {
//二叉樹的層序遍歷
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
let depth = 1;
while (queue.length !== 0) {
// 記錄當(dāng)前層級(jí)節(jié)點(diǎn)數(shù)
let length = queue.length;
depth++
//存放每一層的節(jié)點(diǎn)
let curLevel = [];
while (length--) {
let node = queue.shift();
curLevel.push(node.val);
// 存放當(dāng)前層下一層的節(jié)點(diǎn)
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
//把每一層的結(jié)果放到結(jié)果數(shù)組
if (depth % 2 === 0) {
res.push(curLevel);
} else {
res.push(curLevel.reverse());
}
}
return res;
};
107. 二叉樹的層序遍歷 II
最后返回的結(jié)果，就是層序遍歷的倒敘。那么我們只需要修改一行代碼趋厉，即可 AC 本題寨闹。
ar levelOrderBottom = function(root) {
//二叉樹的層序遍歷
let res=[],queue=[];
queue.push(root);
if(root===null){
return res;
}
while(queue.length!==0){
// 記錄當(dāng)前層級(jí)節(jié)點(diǎn)數(shù)
let length=queue.length;
//存放每一層的節(jié)點(diǎn)
let curLevel=[];
for(let i=0;i<length;i++){
let node=queue.shift();
curLevel.push(node.val);
// 存放當(dāng)前層下一層的節(jié)點(diǎn)
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
}
//把每一層的結(jié)果放到結(jié)果數(shù)組
res.push(curLevel);
}
return res.reverse();
};
111. 二叉樹的最小深度
什么時(shí)候可以返回呢？就是當(dāng)當(dāng)前節(jié)點(diǎn)既沒有左孩子也沒有右孩子的時(shí)候觅廓。我們可以記錄當(dāng)前遍歷的層數(shù)鼻忠，當(dāng)遇到第一個(gè)葉子結(jié)點(diǎn)的時(shí)候，停止遍歷杈绸，返回層數(shù)帖蔓。
var minDepth = function(root) {
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
let depth = 0
while (queue.length !== 0) {
// 記錄當(dāng)前層級(jí)節(jié)點(diǎn)數(shù)
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. 二叉樹的最大深度
使用變量，記錄當(dāng)前遍歷的層數(shù)
var maxDepth = function(root) {
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
let depth = 0
while (queue.length !== 0) {
// 記錄當(dāng)前層級(jí)節(jié)點(diǎn)數(shù)
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 的那種瞳脓。之前放入的是數(shù)組塑娇，那就數(shù)組的平均值，就很簡單了劫侧。
var averageOfLevels = function(root) {
//二叉樹的層序遍歷
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
while (queue.length !== 0) {
// 記錄當(dāng)前層級(jí)節(jié)點(diǎn)數(shù)
let length = queue.length;
//存放每一層的節(jié)點(diǎn)
let curLevel = [];
while (length--) {
let node = queue.shift();
curLevel.push(node.val);
// 存放當(dāng)前層下一層的節(jié)點(diǎn)
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
//把每一層的結(jié)果放到結(jié)果數(shù)組
res.push(curLevel.reduce((a, b) => a + b) / curLevel.length);
}
return res;
};
429. N 叉樹的層序遍歷
對(duì)于 N 叉樹埋酬，則是對(duì)該節(jié)點(diǎn)的孩子結(jié)點(diǎn)進(jìn)行遍歷。
var levelOrder = function(root) {
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
while (queue.length !== 0) {
// 記錄當(dāng)前層級(jí)節(jié)點(diǎn)數(shù)
let length = queue.length;
//存放每一層的節(jié)點(diǎn)
let curLevel = [];
while (length--) {
let node = queue.shift();
curLevel.push(node.val);
// 存放當(dāng)前層下一層的節(jié)點(diǎn)
for (let item of node.children) {
item && queue.push(item)
}
}
//把每一層的結(jié)果放到結(jié)果數(shù)組
res.push(curLevel);
}
return res;
};
199. 二叉樹的右視圖
當(dāng) length 不存在時(shí)烧栋，則就證明到達(dá)最后一個(gè)結(jié)點(diǎn)写妥，此時(shí)即為右結(jié)點(diǎn)
var rightSideView = function(root) {
//二叉樹的層序遍歷
let res=[],queue=[];
queue.push(root);
if(root===null){
return res;
}
while(queue.length!==0){
// 記錄當(dāng)前層級(jí)節(jié)點(diǎn)數(shù)
let length=queue.length;
while(length--){
let node=queue.shift();
if(!length) {
res.push(node.val)
}
// 存放當(dāng)前層下一層的節(jié)點(diǎn)
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
}
}
return res;
};
515. 在每個(gè)樹行中找最大值
這道題也是屬于改一行代碼，就可以 AC 的审姓。
var largestValues = function(root) {
//二叉樹的層序遍歷
let res = [], queue = [];
queue.push(root);
if (root === null) {
return res;
}
while (queue.length !== 0) {
// 記錄當(dāng)前層級(jí)節(jié)點(diǎn)數(shù)
let length = queue.length;
//存放每一層的節(jié)點(diǎn)
let curLevel = [];
while (length--) {
let node = queue.shift();
curLevel.push(node.val);
// 存放當(dāng)前層下一層的節(jié)點(diǎn)
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
//把每一層的結(jié)果放到結(jié)果數(shù)組
res.push(Math.max.apply(null, curLevel));
}
return res;
};
116. 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針
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. 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針 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;
};
