637. 二叉树的层平均值-深度优先遍历+层次遍历-力扣双百代码

637. 二叉树的层平均值-深度优先遍历+层次遍历-力扣双百代码

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

这题应该算是一个很不错的题目了，因为在遇到树的问题时，可能能够从这题种提取一些经验，感兴趣可以学习一下，解题代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

 int high_tree(struct TreeNode* root){
     if(root){
         return fmax(high_tree(root->left),high_tree(root->right))+1;
     }
     else{
         return 0;
     }
 }
 #define size  1000
double* averageOfLevels(struct TreeNode* root, int* returnSize){
    struct TreeNode*Queue[size],*p;
    int rear=0,front=0;
    int high=high_tree(root);
    double* re=(double*)malloc(sizeof(double)*high);
     double resize[high];
     for(int i=0;i<high;i++){
         re[i]=0;
         resize[i]=0;
     }
     printf("%d ",high);

    Queue[rear]=root;
    rear=(rear+1)%size;
      Queue[rear]=NULL;
    rear=(rear+1)%size;
    int now_high=0;
    while(rear!=front){
         printf("now high %d ",now_high);
        p=Queue[front];
        front=(front+1)%size;
        if(p==NULL&&rear==front){
            break;
        }
        if(p==NULL){
            Queue[rear]=NULL;
             rear=(rear+1)%size;
             now_high++;
            

        }
        else{
             re[now_high]=re[now_high]+p->val;
            resize[now_high]++;
            if(p->left){
                Queue[rear]=p->left;
                rear=(rear+1)%size;
                
            }
            if(p->right){
                Queue[rear]=p->right;
                rear=(rear+1)%size;

            }

        }
        

    }
*returnSize=high;
for(int i=0;i<high;i++){
    re[i]=re[i]/(resize[i]*1.0);

}

    return re;



}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83