50108. Sequence to Binary Tree
難度：4/5
Second Try: 3/5 Used Time: 17:55
有點小複雜，注意cmp不要直return大於的結果，1, 0, -1都要討論。
Second Try: 3/5 Used Time: 13:541
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#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include "construct.h"
// typedef struct node{
// int value;
// struct node *left, *right;
// } Node;
int b[16384] = {0};
int cmp(const void* a, const void* b){
return (*(int*)b) - (*(int*)a);
}
Node* ConstructTree(int s[], int n){
if(n == 0) return NULL;
if(n < MAXLENGTH){
Node* head = (Node*) malloc(sizeof(Node));
head->left = NULL, head->right = NULL;
Node* p = head;
for(int i = n - 1; i >= 0; i--){
Node* cur = (Node*) malloc(sizeof(Node));
cur->value = s[i];
p->left = cur;
p->right = NULL;
p = cur;
}
p->left = NULL, p->right = NULL;
return head->left;
}
memcpy(b, s, sizeof(int) * n);
qsort(b, n, sizeof(int), cmp);
int root_val = b[MAXLENGTH - 1];
int idx;
for(idx = 0; idx < n; idx++){
if(s[idx] == root_val) break;
}
Node* root = (Node*) malloc(sizeof(Node));
root->value = root_val;
root->left = ConstructTree(s, idx);
root->right = ConstructTree(s + idx + 1, n - idx - 1);
return root;
}