永州建设网站公司,wordpress菜单分类,wordpress 仿站 主题,南京网站制作公司报价思路
使用队列:
初始化的时候,将root, push进队列q中循环队列q,当其中不为空时,取出第一个元素(q.shift),记为r若r.left不为空,将r.left推进q,若r.right不为空,将r.right推进q
记录层次: 4. 初始化设置i 0; 5. 在入队的时候,入队一个对象{r: root, i} 6. 出队时,使用es6的解…
思路
使用队列:
初始化的时候,将root, push进队列q中循环队列q,当其中不为空时,取出第一个元素(q.shift),记为r若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);}}
}上面基本上已经实现了层次遍历下面新增一个返回数组,实现题目需求
现在拥有的是层号和每层的值.接下来将每层的层号和值作为键值对放入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
