思路

使用隊列:

1. 初始化的時候,將root, push進隊列q中
2. 循環隊列q,當其中不為空時,取出第一個元素(q.shift),記為r
3. 若r.left不為空,將r.left推進q,若r.right不為空,將r.right推進q

記錄層次:
4. 初始化設置i =0;
5. 在入隊的時候,入隊一個對象{r: root, i}
6. 出隊時,使用es6的解構賦值取出 {r , i}

• 實現如下:

var averageOfLevels = function (root) {let q = []; 		// 隊列let i = 0;		// 記錄層次用的標記q.push({r: root, i});		// 將根放入隊列中while(q.length > 0) {		// 隊列不為空let { r, i } = q.shift();		// 得到根和層次信息if(r) {		// 根不為空i++;		// 層次加1if(r.left) {		// 左孩子不為空q.push(r.left);}if(r.right) {.push(r.right);		}console.log(r.val, i);}}
}

• 上面基本上已經實現了層次遍歷
• 下面新增一個返回數組,實現題目需求

1. 現在擁有的是層號和每層的值.
2. 接下來將每層的層號和值作為鍵值對放入map結構中.

var averageOfLevels = function (root) {let q = [];let i = 0;let map = new Map;q.push({ r: root, i });while (q.length > 0) {let { r, i } = q.shift();if (r) {i++;if (r.left) {q.push({ r: r.left, i });}if (r.right) {q.push({ r: r.right, i });}// 改動部分, 使用map結構存儲層次的 鍵值對if(map.has(i)){let arr = map.get(i);arr.push(r.val);map.set(i, arr);} else{map.set(i,[r.val]);}}}for(let [i, key] of map){console.log(i, key);}
};

• 上面完成了將每層的層號和值作為鍵值對放入map結構中.
• 下面修改末尾的for(let [i, key] of map)內部,使其滿足題目的需求

let retArr = [];
for (let [i, key] of map) {let sum = 0;if (key.length > 1) {for (let i = 0; i < key.length; i++) {sum += key[i];}} else {sum = key[0];}retArr[i - 1] = sum / key.length;
}
return retArr