50182. Two Lists to Tree
難度：3.5/5
17行的if(p == NULL) return NULL;記得要加，不然他會找不到要切哪裡。
Second Try: 4/5 Used Time: 16:251
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#include <stdio.h>
#include "BuildTree.h"
// typedef struct Node{
// int val;
// struct Node *left, *right;
// } Node;
int count_nodes(Node* p){
int n = 0;
while(p != NULL) n++, p = p->left;
return n;
}
Node* cut(Node* p){
int cnt = count_nodes(p);
if(p == NULL) return NULL;
int first;
if(cnt % 2 == 0) first = cnt / 2;
else first = (cnt + 1) / 2;
Node *temp = p;
for(int i = 0; i < first - 1; i++){
temp = temp->left;
}
Node* s = temp->left;
temp->left = NULL;
return s;
}
void print_node(Node* p){
if(p == NULL){
printf("=null=\n");
return;
}
while(p != NULL){
printf("%d ", p->val);
p = p->left;
}
printf("\n");
}
Node* BuildTree(Node* list1, Node* list2){
// print_node(list1);
// print_node(list2);
if(list1 == NULL && list2 == NULL){
// printf("12 null\n");
return NULL;
}
else if(list1 == NULL){
// printf("l null\n");
return list2;
}
else if(list2 == NULL){
// printf("2 null\n");
return list1;
}
else{
Node* root;
if(list1->val < list2->val){
root = list1;
list1 = list1->left;
}
else{
root = list2;
list2 = list2->left;
}
// printf("root val %d\n", root->val);
Node *r1 = cut(list1);
Node *r2 = cut(list2);
// printf("left:\n");
// print_node(list1);
// print_node(list2);
// printf("right:\n");
// print_node(r1);
// print_node(r2);
root->left = BuildTree(list1, list2);
root->right = BuildTree(r1, r2);
return root;
}
}