50074. Tree Statistics
難度：4.5/5
call四個遞迴會超時，想辦法把壓成3或2個。
Second Try: 3/5 Used Time: 10:35 Using 1 recursive function is enough.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#include <stdio.h>
#include <stdlib.h>
#include "trace.h"
static inline int max(int a, int b){
if(a > b) return a;
return b;
}
int internal = 0;
int leaf = 0;
int count_max_branch(Node* root){
if(root == NULL) return 0;
if(root->list == NULL){
leaf++;
return 0;
}
internal++;
int this_branch = 0;
int max_num = 0;
ChildList* now = root->list;
while(now){
max_num = max(max_num, count_max_branch(now->node));
now = now->next;
this_branch++;
}
max_num = max(max_num, this_branch);
return max_num;
}
int count_depth(Node* root){
if(root == 0) return 0;
if(root->list == NULL) return 0;
int max_depth = 0;
ChildList* now = root->list;
while(now){
max_depth = max(max_depth, count_depth(now->node));
now = now->next;
}
return max_depth + 1;
}
void trace(Node *root, Answer *ans){
ans->MaxBranchFactor = count_max_branch(root);
ans->Depth = count_depth(root);
ans->InternalNode = internal;
ans->Leaf = leaf;
}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#include <stdio.h>
#include <stdlib.h>
#include "trace.h"
static inline int max(int a, int b){
if(a > b) return a;
return b;
}
int now_d = -1;
void trace(Node *root, Answer *ans){
now_d++;
if(root->list != NULL) (ans->InternalNode)++;
else (ans->Leaf)++;
ChildList* now = root->list;
int this_b = 0;
while(now){
trace(now->node, ans);
now = now->next;
this_b++;
}
ans->MaxBranchFactor = max(ans->MaxBranchFactor, this_b);
ans->Depth = max(ans->Depth, now_d);
now_d--;
}