49 lines
1.5 KiB
JavaScript
49 lines
1.5 KiB
JavaScript
/**
|
||
* Definition for a binary tree node.
|
||
* function TreeNode(val, left, right) {
|
||
* this.val = (val===undefined ? 0 : val)
|
||
* this.left = (left===undefined ? null : left)
|
||
* this.right = (right===undefined ? null : right)
|
||
* }
|
||
*/
|
||
/**
|
||
* @param {TreeNode} root
|
||
* @return {number[]}
|
||
* https://leetcode.cn/problems/average-of-levels-in-binary-tree/?envType=study-plan-v2&envId=top-interview-150
|
||
*/
|
||
const averageOfLevels = function (root) {
|
||
|
||
};
|
||
|
||
/*
|
||
直接层序遍历，之后对每一层的数据求和，再求平均数(保留五位小数)
|
||
*/
|
||
function f1(root) {
|
||
const queue = [root];
|
||
const ans = [];
|
||
|
||
while (queue.length > 0) {
|
||
const n = queue.length;
|
||
let sum = 0; // 每一层数据的和
|
||
|
||
// 遍历每一层的所有数据，对它们求和
|
||
for (let i = 0; i < n; i++) {
|
||
const node = queue.shift();
|
||
sum += node.val;
|
||
// 将左右子节点存入下一层
|
||
if (node.left) queue.push(node.left);
|
||
if (node.right) queue.push(node.right);
|
||
}
|
||
|
||
// 求平均数，保留五位小数，并存入结果集
|
||
ans.push(Number((sum / n).toFixed(5)));
|
||
}
|
||
return ans;
|
||
}
|
||
|
||
/*
|
||
使用DFS来遍历，利用一个数组levelData保存如下数据，数组元素的下标表示每一层的信息，元素为一个对象{sum: 这层元素的和, count: 这层元素个数}
|
||
dfs的时候如果当前层数level小于leveData.length，表示这是新层的第一个数据，就levelData.push({sum: curNode.val, count:1})
|
||
*/
|
||
// TODO:
|