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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// begin
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
#define VECTOR_DEF(T) \
typedef struct { \
T* buffer; \
int size; \
int cap; \
} T##Vector; \
\
void T##Vector_init(T##Vector *self); \
void T##Vector_push_back(T##Vector *self, T elem); \
void T##Vector_insert_before(T##Vector *self, int n, T elem); \
void T##Vector_pop(T##Vector *self); \
bool T##Vector_empty(T##Vector *self); \
void T##Vector_remove(T##Vector *self, size_t n); \
size_t T##Vector_len(T##Vector *self); \
T* T##Vector_begin(T##Vector *self); \
T* T##Vector_last(T##Vector *self); \
T* T##Vector_end(T##Vector *self); \
T* T##Vector_ref(T##Vector *self, size_t n); \
void T##Vector_swap(T##Vector *self, int i, int j); \
T##Vector T##Vector_move(T##Vector *self); \
void T##Vector_free(T##Vector *self);
#define VECTOR_IMPL(T) \
void T##Vector_init(T##Vector *self) { \
self->buffer = (T*)malloc(sizeof(T) * 16); \
self->cap = 16; \
self->size = 0; \
} \
\
void T##Vector_push_back(T##Vector *self, T elem) { \
if (self->size + 1 > self->cap) { \
self->buffer = realloc(self->buffer, sizeof(T) * self->cap * 2); \
self->cap *= 2; \
} \
self->buffer[self->size] = elem; \
self->size += 1; \
} \
void T##Vector_insert_before(T##Vector *self, int n, T elem) { \
if (n < 0 || n > self->size) { \
return; \
} \
if (self->size + 1 > self->cap) { \
self->buffer = malloc(sizeof(T) * self->cap * 2); \
self->cap *= 2; \
} \
if (n != self->size) { \
memmove(self->buffer + n + 1, \
self->buffer + n, \
sizeof(T) * (self->size - n)); \
self->buffer[n] = elem; \
self->size += 1; \
} \
} \
void T##Vector_pop(T##Vector *self) { \
self->size -= 1; \
} \
void T##Vector_remove(T##Vector *self, size_t n) { \
if (n < 0 || n >= self->size) return; \
memmove(self->buffer + n, \
self->buffer + n + 1, \
sizeof(T) * self->size - n - 1); \
self->size -= 1; \
} \
T* T##Vector_begin(T##Vector *self) { return self->buffer; } \
bool T##Vector_empty(T##Vector *self) { return self->size == 0; } \
T* T##Vector_end(T##Vector *self) { return self->buffer + self->size; } \
T* T##Vector_last(T##Vector *self) { return self->buffer + self->size - 1; } \
T* T##Vector_ref(T##Vector *self, size_t n) { return self->buffer + n; } \
void T##Vector_swap(T##Vector *self, int i, int j) { \
T buf; \
memcpy(&buf, self->buffer + i, sizeof(T)); \
memcpy(self->buffer + i, self->buffer + j, sizeof(T)); \
memcpy(self->buffer + j, &buf, sizeof(T)); \
} \
T##Vector T##Vector_move(T##Vector *self) { \
T##Vector dup = *self; \
self->buffer = NULL; \
self->size = 0; \
self->cap = 0; \
return dup; \
} \
size_t T##Vector_len(T##Vector *self) { return self->size; } \
void T##Vector_free(T##Vector *self) { free(self->buffer); }
typedef int Int;
VECTOR_DEF(Int);
VECTOR_IMPL(Int);
void inorderTraversalImpl(struct TreeNode* node, IntVector *vec) {
if (node == NULL) return;
inorderTraversalImpl(node->left, vec);
IntVector_push_back(vec, node->val);
inorderTraversalImpl(node->right, vec);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
IntVector vec;
IntVector_init(&vec);
inorderTraversalImpl(root, &vec);
*returnSize = IntVector_len(&vec);
return vec.buffer;
}
|
