ARTS是
由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS），至少坚持一年。
ARTS 020
这是第20篇
Algorihm 算法题
637. Average of Levels in Binary Tree
Difficulty Easy
Example 1:
Note:
Input:
3
/ \
9 20
/ \
15 7
Output: [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
Language: C
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
void masprin (double *mas, int nums);
int Depf_tree(struct TreeNode *root);
double Diver (struct TreeNode *root, int depf, int cur_depf);
int Diver_2 (struct TreeNode *root, int depf, int cur_depf);
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
方法1：应该是最容易想到的方法，一层一层的计算；计算本层的同时把下层的节点存储起来。
//计算深度
int LevelsTree(struct TreeNode* root){
if (root == NULL) {
return 0;
}
int lefLevels = LevelsTree(root->left);
int rightLevels = LevelsTree(root->right);
return lefLevels > rightLevels ? lefLevels + 1 : rightLevels + 1 ;
}
double* averageOfLevels(struct TreeNode* root, int* returnSize) {
*returnSize = LevelsTree(root);//树的深度
if (* returnSize == 0) {
return NULL;
}
double* averageOfLevels = (double*)malloc(sizeof(double) * (*returnSize));
struct TreeNode** levels = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1);
levels[0] = root;
int index = 0;
int preindex = index;
for(int i =0;i< *returnSize;i++){
int j = 0;
double sum = 0;
int count = 0;
struct TreeNode** tempLevels = NULL;
struct TreeNode* t = levels[j];;
while (t != NULL) {
sum = sum + t->val;
count++;
if (t->left) {
if (tempLevels == NULL) {
tempLevels = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1);
tempLevels[index] = t->left;
}
else{
++index;
tempLevels = (struct TreeNode**)realloc(tempLevels,sizeof(struct TreeNode*)*(index+1));
tempLevels[index] = t->left;
}
}
if (t->right) {
if (tempLevels == NULL) {
tempLevels = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1);
tempLevels[index] = t->right;
}
else{
++index;
tempLevels = (struct TreeNode**)realloc(tempLevels,sizeof(struct TreeNode*)*(index+1));
tempLevels[index] = t->right;
}
}
//
++j;
if (j<=preindex) {
t = levels[j];
}
else{
t = NULL;
}
}
preindex = index;
index = 0;
averageOfLevels[i] = sum/count;
if (levels != NULL) {
free(levels);
levels = NULL;
}
levels = tempLevels;
}
if (levels != NULL) {
free(levels);
levels = NULL;
}
return averageOfLevels;
}
以下是别人的实现，可以学习一下 方法2: 这个实现也是一层一层计算的，但是实现比我的要简单一点，他在计算深度的同时直接计算出了每一层的节点总和，缺点就是使用了固定数值和全局变量。
double lv[10000];
int lc[10000];
int size;
void dfs(struct TreeNode* root, int level) {
if(root == 0) return;
if(level > size) {
size = level;
}
lv[level] += (double)root->val;
lc[level]++;
dfs(root->left, level+1);
dfs(root->right, level+1);
}
double* averageOfLevels(struct TreeNode* root, int* returnSize) {
for(int i = 0; i < 10000; i++) {
lv[i] = lc[i] = 0;
}
size = -1;
dfs(root, 0);
if(size == -1) return 0;
double* res = (double *)malloc(sizeof(double) * size+1);
for(int i = 0; i <= size; i++) {
res[i] = lv[i] / lc[i];
}
*returnSize = size+1;
return res;
}
方法3： 这个实现和上一个的思路是一样的，但是我觉得要比上一个实现优雅，
int GetTreeDepth(struct TreeNode* root){
int LDepth, RDepth;
LDepth = 0;
RDepth = 0;
if(!root) return 0;
if(root->left) LDepth = GetTreeDepth(root->left);
if(root->right) RDepth = GetTreeDepth(root->right);
return (LDepth > RDepth ? LDepth : RDepth) + 1;
}
void GetPerLevel(struct TreeNode* root, double* sum, int *num, int Level) {
if(!root) return;
sum[Level] += (double)(root->val);
num[Level]++;
Level++;
if(root->left) GetPerLevel(root->left, sum, num, Level);
if(root->right) GetPerLevel(root->right, sum, num, Level);
return;
}
double* averageOfLevels(struct TreeNode* root, int* returnSize) {
int Level = 0;
*returnSize = GetTreeDepth(root);
double *sum = (double *)malloc(sizeof(double) * *returnSize);
int *num = (int *)malloc(sizeof(int) * *returnSize);
memset(sum, 0, sizeof(double) * *returnSize);
memset(num, 0, sizeof(int) * *returnSize);
GetPerLevel(root, sum, num, Level);
for(int i = 0; i < *returnSize; i++) sum[i] /= num[i];
return sum;
}
Review
优化iOS App启动时间： https://dandan2009.github.io/2018/12/18/optimizing-app-startup-time/
TIPS
以下两种写法都是5秒钟之后执行动画，但是带来的效果却不一样。第一种写法会被tableview刷新打断，导致提前执行，直接变成动画之后的状态，后一种就不会，为什么？ 后来发现在动画执行的过程中如果有UI重绘的操作，也会导致动画中断。为什么？
[UIView animateWithDuration:0.5 delay:5.0 options:(UIViewAnimationOptionAllowUserInteraction) animations:^{
weakSelf.coverView.frame = (CGRect){0,5,weakSelf.width,weakSelf.height};
weakSelf.loadImg.frame = (CGRect){weakSelf.width/4,weakSelf.height,weakSelf.width/2,weakSelf.width/2/16*7};
} completion:^(BOOL finished) {
}];
和
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(5 * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
[UIView animateWithDuration:0.5 delay:0 options:(UIViewAnimationOptionAllowUserInteraction) animations:^{
weakSelf.coverView.frame = (CGRect){0,5,weakSelf.width,weakSelf.height};
weakSelf.loadImg.frame = (CGRect){weakSelf.width/4,weakSelf.height,weakSelf.width/2,weakSelf.width/2/16*7};
} completion:^(BOOL finished) {
}];
});
Share
最近好多公司都在裁员，新浪成都全体裁,美团深圳全体裁，飞利浦技术全部裁，点融成都全裁，我们公司据说裁百分之十。 真的互联网走下坡路了吗？
