[杂七杂八] LeetCode 637. Average of Levels in Binary Tree

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example:Input:    3   / \  9  20    /  \   15   7Output: [3, 14.5, 11]Explanation:The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Solution

//题目意思就是统计二叉树每一层的平均数//我的做法是利用k标记层数，中序遍历的同时更新每一层的节点数和总和，最后返回平均值数组，代码如下double* averageOfLevels(struct TreeNode* root, int* returnSize) {    double *sum = (double *)malloc(sizeof(double) * 1000000);    memset(sum,0,sizeof(sum));    int num[10000] = {0};    *returnSize = 0;    getArray(root,returnSize,1,sum,num);    for (int i = 0;i < *returnSize;i++) {        sum[i] /= num[i];    }    return sum;}void getArray(struct TreeNode* root,int *returnSize,int k,double *sum,int *num){    if (!root)         return;    if (k > *returnSize)         *returnSize = k;    sum[k - 1] += root->val;    num[k - 1]++;    getArray(root->left,returnSize,k + 1,sum,num);    getArray(root->right,returnSize,k + 1,sum,num);    return ;}