forked from lennylxx/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
222.c
68 lines (52 loc) · 1.27 KB
/
222.c
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
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int countNodes(struct TreeNode* root) {
if (root == NULL) return 0;
struct TreeNode *l = root->left;
struct TreeNode *r = root->right;
int most_left_height = 1;
int most_right_height = 1;
while (l != NULL) {
l = l->left;
most_left_height++;
}
while (r != NULL) {
r = r->right;
most_right_height++;
}
if (most_left_height == most_right_height) { /* it's a full binary tree */
return (1 << most_left_height) - 1;
}
else {
return countNodes(root->left) + countNodes(root->right) + 1;
}
}
int main() {
struct TreeNode *r = (struct TreeNode *)calloc(9, sizeof(struct TreeNode));
struct TreeNode *p = r;
int i;
for (i = 1; i <= 9; i++) {
p->val = i;
p++;
}
p = r;
p->left = r + 1;
p->right = r + 2;
p = r + 1;
p->left = r + 3;
p->right = r + 4;
p = r + 2;
p->left = r + 5;
p->right = r + 6;
p = r + 3;
p->left = r + 7;
p->right = r + 8;
/* should be 9 */
printf("%d\n", countNodes(r));
return 0;
}