当前位置：首页 > ds >正文

leetcode刷题日记——二叉树的层平均值

ds 2025/8/21 13:17:19

[ 题目描述 ]：
在这里插入图片描述

[ 思路 ]：

BFS，通过层次遍历求得每层的和，然后取平均数，存入结果数组
树中节点个数在1-10000之间，那么结果数组最大为10000个结果，层数最多为 2ⁿ-1>10000，可以推出 n 最小为 14，即 14层，那么最多的那层节点为 2¹³ = 8096个
由此，可得出以下代码
运行如下

[ 官方题解 ]：

方法一：深度优先搜索，需要维护两个数组，counts 用于存储二叉树的每一层的节点数，sums 用于存储二叉树的每一层的节点值之和。搜索过程中需要记录当前节点所在层，如果访问到的节点在第 i 层，则将 counts[i] 的值加 1，并将该节点的值加到 sums[i]。

int countsSize;
int sumsSize;void dfs(struct TreeNode* root, int level, int* counts, double* sums) {if (root == NULL) {return;}if (level < sumsSize) {sums[level] += root->val;counts[level] += 1;} else {sums[sumsSize++] = (double)root->val;counts[countsSize++] = 1;}dfs(root->left, level + 1, counts, sums);dfs(root->right, level + 1, counts, sums);
}double* averageOfLevels(struct TreeNode* root, int* returnSize) {countsSize = sumsSize = 0;int* counts = malloc(sizeof(int) * 1001);double* sums = malloc(sizeof(double) * 1001);dfs(root, 0, counts, sums);double* averages = malloc(sizeof(double) * 1001);*returnSize = sumsSize;for (int i = 0; i < sumsSize; i++) {averages[i] = sums[i] / counts[i];}return averages;
}