637. 二叉树的层平均值

Posted on In Views: Disqus:
LeetCode刷题系列。

描述

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

示例 1:

1
2
3
4
5
6
7
8
9
10
输入:
    3
   / \
  9  20
    /  \
   15   7
输出: [3, 14.5, 11]

解释:
第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].

注意：

节点值的范围在32位有符号整数范围内。

来源：力扣（LeetCode）
链接：637. Average of Levels in Binary Tree

解题思路

本题依然考察二叉树的层次遍历，可以在102. 二叉树的层次遍历的基础上将各层数据的平均值求出来。

首先来看迭代的解法，具体见解法一，里面有详细的注释。

换一种循环的方式，可以有另外一种迭代的解法，具体见解法二。

如果采用递归的话，显然本题要写一个辅助函数，思考要传入什么参数，是传值还是传引用，需不需要返回参数，需要的话要返回什么参数等等的问题。

代码

解法一：迭代

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**
 * 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().
 */

// 定义队列最大容量
#define QMAX 10024
typedef struct TreeNode* Tree;

typedef struct Queue
{
    // 保存树节点的指针
    Tree Node[QMAX];
    int front;
    int rear;
}Queue;

//队列初始化
void Qinit(Queue *q)
{
    q->front = q->rear = 0;
 
}

//判断队列是否已满
bool isFull(Queue *q)
{
    return ((q->rear + 1) % QMAX == q->front);
}

//判断队列是否为空
bool isEmpty(Queue *q)
{
    return q->rear == q->front;
}

//入队
bool push(Queue *q, Tree node)
{
  
    if(isFull(q))
        return false;
    
    q->Node[q->rear] = node;
    q->rear = (q->rear + 1) % QMAX;
    return true;
}


Tree pop(Queue *q)
{
    if(isEmpty(q))
    {
        return NULL;
    }
    
    Tree node;
    //存储队列头元素
    node = q->Node[q->front];
    q->front = (q->front + 1) % QMAX;
    return node;
}



double* averageOfLevels(struct TreeNode* root, int* returnSize)
{
    int count = 0, size = 0;
    //用来存储每一层的总数
    double sum;
    //用来存每一层的平均数
    double* ave = (double *)malloc(sizeof(double) * QMAX);  
    *returnSize = 0;
    //队列初始化
    Queue queue;
    Qinit(&queue);
    
    //还是要判断一下是否为空，虽然题目说肯定是非空的
    if(!root)  
    {
       return NULL;
    }
    
    //根入队
    else
    {
         push(&queue, root);
        //第一层只有根
         ave[0] = root->val; 
    }
    
    //如果队列不为空，进入层序遍历的大循环
    while(!isEmpty(&queue))  
    {
        //计算这一层的数目
        count = queue.rear - queue.front;  
        size = count;
        sum = 0.0;
        
        //各层元素求和
        while(size > 0) 
        {
            //出队
            root = pop(&queue);
            sum += root->val;
            
            //如果左孩子不为空，访问左孩子
            if(root->left)  
            {
                push(&queue, root->left);
            }
            
            //如果右孩子不为空，访问右孩子
            if(root->right)
            {
                push(&queue, root->right);
            } 
            //当size为0时就说明上一层的元素已经完全删除，每删除一个元素就有可能带两个新元素进队
            size--;  
        }
        //层序遍历求平均
        ave[(*returnSize)++] = sum / count; 
    }
    return ave;  
    
    
}

解法二：迭代

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/**
 * 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().
 */

// 定义队列最大容量
#define QMAX 10024
typedef struct TreeNode* Tree;

typedef struct Queue
{
    // 保存树节点的指针
    Tree Node[QMAX];
    int front;
    int rear;
}Queue;

//队列初始化
void Qinit(Queue *q)
{
    q->front = q->rear = 0;
 
}

//判断队列是否已满
bool isFull(Queue *q)
{
    return ((q->rear + 1) % QMAX == q->front);
}

//判断队列是否为空
bool isEmpty(Queue *q)
{
    return q->rear == q->front;
}

//入队
bool push(Queue *q, Tree node)
{
  
    if(isFull(q))
        return false;
    
    q->Node[q->rear] = node;
    q->rear = (q->rear + 1) % QMAX;
    return true;
}


Tree pop(Queue *q)
{
    if(isEmpty(q))
    {
        return NULL;
    }
    
    Tree node;
    //存储队列头元素
    node = q->Node[q->front];
    q->front = (q->front + 1) % QMAX;
    return node;
}



double* averageOfLevels(struct TreeNode* root, int* returnSize)
{
    int count = 0, size = 0;
    //用来存储每一层的总数
    double sum;
    //用来存每一层的平均数
    double* ave = (double *)malloc(sizeof(double) * QMAX);  
    *returnSize = 0;
    
     //每一层节点的个数分配空间并初始化为1，最多有QMAX层
    int *level = (int *)calloc(1, sizeof(int) * QMAX);
       
    //控制层序遍历时各层的高度，第一层仅为根节点，高度为0
    int height = 0;
    //初始化各层元素个数，第一层仅为根节点，元素个数为1
    level[height] = 1;
    
    //队列初始化
    Queue queue;
    Qinit(&queue);
    
    //还是要判断一下是否为空，虽然题目说肯定是非空的
    if(!root)  
    {
       return NULL;
    }
    
    //根入队
    else
    {
         push(&queue, root);
        //第一层只有根
         ave[0] = root->val; 
    }
      
    //如果队列不空，进入层序遍历的大循环
    while (!isEmpty(&queue)) 
    {   
        //高度+1
        height++; 
        //初始化并记录每一层的元素个数
        count = level[height - 1];
        //每次层序遍历都需要将sum清0并赋值
        sum = 0.0;
        
        //各层元素的循环输出到result二维表
        for (int i = 0; i< level[height - 1]; i++)
        {   
            //从队列中取出一个元素
            root = pop(&queue);
            //各层元素求和
            sum += root->val;
 
            //如果左孩子非空访问左孩子
            if (root->left)
            {
                push(&queue, root->left);
                //这个很重要，更新层的高度
                level[height]++;
            }
            //如果右孩子非空访问右孩子
            if (root->right)
            {
                push(&queue, root->right);
                level[height]++;
            }
        }
    
        //层序遍历求平均
        ave[(*returnSize)++] = sum / count; 
    }
    return ave;  
     
}

解法三：递归

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
/**
 * 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().
 */

typedef struct TreeNode* Tree;

int max(int a, int b)
{
    if(a > b) return a;
    else return b;
}

int maxDepth(Tree root)
{
    if(!root)
        return 0;
    else
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

/*递归函数
入参：
树的根节点：root
树的层数：count
各层总和：result
各层元素个数：floorSize
*/
void averageOfLevelsHelper(Tree root, int count, double* result, int* floorSize) 
{
    //如果树为空，直接返回
    if (!root) return;
    //各层元素个数不断加1
    floorSize[count] += 1;
    //各层元素求和
    result[count] += root->val;
    //层数递增
    ++count;
    //左递归调用
    averageOfLevelsHelper(root->left, count, result, floorSize);
    //右递归调用
    averageOfLevelsHelper(root->right, count, result, floorSize);
}

double* averageOfLevels(Tree root, int* returnSize)
{
    //计算二叉树的层数
    int count = maxDepth(root);
    double *result = malloc(sizeof(double)*count);
    //分配二叉树各层元素个数
    int *floorSize = malloc(sizeof(int)*count);
    //数据初始化
    memset(result, 0, sizeof(double)*count);
    memset(floorSize, 0, sizeof(int)*count);
    //递归调用
    averageOfLevelsHelper(root, 0, result, floorSize);
    
    *returnSize = count;
    
    //求各层平均数
    for (int i = 0; i < count; ++i) result[i] = result[i]/floorSize[i];
    
    return result;
}

参考