Skip to content

Commit 39261d2

Browse files
begeekmyfriendbegeekmyfriend
committed
Populating next right pointers in each node
Signed-off-by: Leo Ma <begeekmyfriend@gmail.com>
1 parent d7ef7fc commit 39261d2

File tree

4 files changed

+268
-0
lines changed

4 files changed

+268
-0
lines changed

‎116_populating_next_right_pointers_in_each_node/Makefile

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
all:
2+
gcc -O2 -o test connect.c

‎116_populating_next_right_pointers_in_each_node/connect.c

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
#include <stdio.h>
2+
#include <stdlib.h>
3+
4+
struct TreeLinkNode {
5+
int val;
6+
struct TreeLinkNode *left;
7+
struct TreeLinkNode *right;
8+
struct TreeLinkNode *next;
9+
};
10+
11+
static void connect(struct TreeLinkNode *root)
12+
{
13+
struct TreeLinkNode *head = root;
14+
while (head->left != NULL) {
15+
struct TreeLinkNode *p;
16+
for (p = head; p != NULL; p = p->next) {
17+
p->left->next = p->right;
18+
p->right->next = p->next == NULL ? NULL : p->next->left;
19+
}
20+
head = head->left;
21+
}
22+
}
23+
24+
int main(int argc, char **argv)
25+
{
26+
struct TreeLinkNode root, n1[2], n2[4], n3[8];
27+
root.val = 5;
28+
n1[0].val = 4;
29+
n1[1].val = 8;
30+
n2[0].val = 11;
31+
n2[2].val = 13;
32+
n2[3].val = 4;
33+
n3[0].val = 7;
34+
n3[1].val = 2;
35+
n3[6].val = 5;
36+
n3[7].val = 1;
37+
38+
root.left = &n1[0];
39+
root.right = &n1[1];
40+
n1[0].left = &n2[0];
41+
n1[0].right = NULL;
42+
n1[0].next = NULL;
43+
n1[1].left = &n2[2];
44+
n1[1].right = &n2[3];
45+
n1[1].next = NULL;
46+
n2[0].left = &n3[0];
47+
n2[0].right = &n3[1];
48+
n2[0].next = NULL;
49+
n2[2].left = NULL;
50+
n2[2].right = NULL;
51+
n2[2].next = NULL;
52+
n2[3].left = &n3[6];
53+
n2[3].right = &n3[7];
54+
n2[3].next = NULL;
55+
n3[0].left = NULL;
56+
n3[0].right = NULL;
57+
n3[0].next = NULL;
58+
n3[1].left = NULL;
59+
n3[1].right = NULL;
60+
n3[1].next = NULL;
61+
n3[6].left = NULL;
62+
n3[6].right = NULL;
63+
n3[6].next = NULL;
64+
n3[7].left = NULL;
65+
n3[7].right = NULL;
66+
n3[7].next = NULL;
67+
68+
connect(&root);
69+
return 0;
70+
}

‎117_populating_next_right_pointers_in_each_node_ii/Makefile

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
all:
2+
gcc -O2 -o test connect.c

‎117_populating_next_right_pointers_in_each_node_ii/connect.c

Lines changed: 194 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,194 @@
1+
#include <stdio.h>
2+
#include <stdlib.h>
3+
4+
struct TreeLinkNode {
5+
int val;
6+
struct TreeLinkNode *left;
7+
struct TreeLinkNode *right;
8+
struct TreeLinkNode *next;
9+
};
10+
11+
#define container_of(ptr, type, member) \
12+
((type *)((char *)(ptr) - (size_t)&(((type *)0)->member)))
13+
14+
#define list_entry(ptr, type, member) \
15+
container_of(ptr, type, member)
16+
17+
#define list_first_entry(ptr, type, field) list_entry((ptr)->next, type, field)
18+
#define list_last_entry(ptr, type, field) list_entry((ptr)->prev, type, field)
19+
20+
#define list_for_each(p, head) \
21+
for (p = (head)->next; p != (head); p = p->next)
22+
23+
#define list_for_each_safe(p, n, head) \
24+
for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next)
25+
26+
struct list_head {
27+
struct list_head *next, *prev;
28+
};
29+
30+
static inline void INIT_LIST_HEAD(struct list_head *list)
31+
{
32+
list->next = list->prev = list;
33+
}
34+
35+
static inline int list_empty(const struct list_head *head)
36+
{
37+
return (head->next == head);
38+
}
39+
40+
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
41+
{
42+
next->prev = new;
43+
new->next = next;
44+
new->prev = prev;
45+
prev->next = new;
46+
}
47+
48+
static inline void list_add(struct list_head *_new, struct list_head *head)
49+
{
50+
__list_add(_new, head, head->next);
51+
}
52+
53+
static inline void list_add_tail(struct list_head *_new, struct list_head *head)
54+
{
55+
__list_add(_new, head->prev, head);
56+
}
57+
58+
static inline void __list_del(struct list_head *entry)
59+
{
60+
entry->next->prev = entry->prev;
61+
entry->prev->next = entry->next;
62+
}
63+
64+
static inline void list_del(struct list_head *entry)
65+
{
66+
__list_del(entry);
67+
entry->next = entry->prev = NULL;
68+
}
69+
70+
struct bfs_node {
71+
struct TreeLinkNode *node;
72+
struct list_head link;
73+
};
74+
75+
static struct bfs_node *node_fetch(struct list_head *free_list, struct TreeLinkNode *node)
76+
{
77+
struct bfs_node *bn = list_first_entry(free_list, struct bfs_node, link);
78+
list_del(&bn->link);
79+
bn->node = node;
80+
return bn;
81+
}
82+
83+
static void queue(struct list_head *parents, struct list_head *children, struct list_head *free_list)
84+
{
85+
struct list_head *p, *n;
86+
struct TreeLinkNode *prev = NULL;
87+
list_for_each_safe(p, n, parents) {
88+
struct bfs_node *new;
89+
struct bfs_node *parent = list_entry(p, struct bfs_node, link);
90+
struct TreeLinkNode *lch = parent->node->left;
91+
struct TreeLinkNode *rch = parent->node->right;
92+
if (lch != NULL) {
93+
if (prev != NULL) {
94+
prev->next = lch;
95+
}
96+
prev = lch;
97+
new = node_fetch(free_list, lch);
98+
list_add_tail(&new->link, children);
99+
}
100+
if (rch != NULL) {
101+
if (prev != NULL) {
102+
prev->next = rch;
103+
}
104+
prev = rch;
105+
new = node_fetch(free_list, rch);
106+
list_add_tail(&new->link, children);
107+
}
108+
109+
/* return */
110+
list_del(p);
111+
list_add(p, free_list);
112+
}
113+
}
114+
115+
static void connect(struct TreeLinkNode *root)
116+
{
117+
if (root == NULL) {
118+
return;
119+
}
120+
121+
struct list_head free_list;
122+
struct list_head q0;
123+
struct list_head q1;
124+
struct bfs_node nodes[4096];
125+
INIT_LIST_HEAD(&free_list);
126+
INIT_LIST_HEAD(&q0);
127+
INIT_LIST_HEAD(&q1);
128+
129+
int i;
130+
for (i = 0; i < 4096; i++) {
131+
list_add(&nodes[i].link, &free_list);
132+
}
133+
134+
int level = 0;
135+
struct bfs_node *new = node_fetch(&free_list, root);
136+
list_add_tail(&new->link, &q0);
137+
138+
while (!list_empty(&q0) || !list_empty(&q1)) {
139+
if (level & 0x1) {
140+
queue(&q1, &q0, &free_list);
141+
} else {
142+
queue(&q0, &q1, &free_list);
143+
}
144+
level++;
145+
}
146+
}
147+
148+
int main(int argc, char **argv)
149+
{
150+
struct TreeLinkNode root, n1[2], n2[4], n3[8];
151+
root.val = 5;
152+
n1[0].val = 4;
153+
n1[1].val = 8;
154+
n2[0].val = 11;
155+
n2[2].val = 13;
156+
n2[3].val = 4;
157+
n3[0].val = 7;
158+
n3[1].val = 2;
159+
n3[6].val = 5;
160+
n3[7].val = 1;
161+
162+
root.left = &n1[0];
163+
root.right = &n1[1];
164+
n1[0].left = &n2[0];
165+
n1[0].right = NULL;
166+
n1[0].next = NULL;
167+
n1[1].left = &n2[2];
168+
n1[1].right = &n2[3];
169+
n1[1].next = NULL;
170+
n2[0].left = &n3[0];
171+
n2[0].right = &n3[1];
172+
n2[0].next = NULL;
173+
n2[2].left = NULL;
174+
n2[2].right = NULL;
175+
n2[2].next = NULL;
176+
n2[3].left = &n3[6];
177+
n2[3].right = &n3[7];
178+
n2[3].next = NULL;
179+
n3[0].left = NULL;
180+
n3[0].right = NULL;
181+
n3[0].next = NULL;
182+
n3[1].left = NULL;
183+
n3[1].right = NULL;
184+
n3[1].next = NULL;
185+
n3[6].left = NULL;
186+
n3[6].right = NULL;
187+
n3[6].next = NULL;
188+
n3[7].left = NULL;
189+
n3[7].right = NULL;
190+
n3[7].next = NULL;
191+
192+
connect(&root);
193+
return 0;
194+
}

0 commit comments

Comments
 (0)