hdu 1622 Trees on the level，hdu1622
原題鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1622
小白書上的題。。。
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstdio>
5 #include<vector>
6 #include<queue>
7 using std::queue;
8 using std::vector;
9 const int Max_N = 260;
10 struct Node {
11 int v, vis;
12 Node *ch[2];
13 inline void set(int _v, Node *p) {
14 vis = 0, v = _v;
15 ch[0] = ch[1] = p;
16 }
17 };
18 struct BinTree {
19 int fail;
20 char buf[Max_N];
21 Node *tail, *root, stack[Max_N];
22 void init() {
23 fail = 0;
24 tail = &stack[0];
25 }
26 inline Node *newNode(int v = 0) {
27 Node *p = tail++;
28 p->set(v, NULL);
29 return p;
30 }
31 inline void insert(const char *src, const int v) {
32 int n = strlen(src);
33 Node *x = root;
34 for (int i = 0; i < n; i++) {
35 if (src[i] == 'L') {
36 if (!x->ch[0]) x->ch[0] = newNode();
37 x = x->ch[0];
38 } else if (src[i] == 'R') {
39 if (!x->ch[1]) x->ch[1] = newNode();
40 x = x->ch[1];
41 }
42 }
43 if (x->vis) fail = 1;
44 x->v = v;
45 x->vis = 1;
46 }
47 inline void bfs() {
48 vector<int> ans;
49 queue<Node *> que;
50 que.push(root);
51 while (!que.empty()) {
52 Node *u = que.front(); que.pop();
53 if (!u->vis) {
54 fail = 1;
55 break;
56 }
57 ans.push_back(u->v);
58 if (u->ch[0]) que.push(u->ch[0]);
59 if (u->ch[1]) que.push(u->ch[1]);
60 }
61 if (fail) {
62 puts("not complete");
63 return;
64 }
65 int n = ans.size();
66 for (int i = 0; i < n; i++) {
67 printf("%d%c", ans[i], i < n - 1 ? ' ' : '\n');
68 }
69 }
70 inline int gogo() {
71 init();
72 int v = 0;
73 root = newNode();
74 for (;;) {
75 if (scanf("%s", buf) != 1) return 0;
76 if (!strcmp(buf, "()")) break;
77 sscanf(&buf[1], "%d", &v);
78 insert(strchr(buf, ',') + 1, v);
79 }
80 bfs();
81 return 1;
82 }
83 }tree;
84 int main() {
85 #ifdef LOCAL
86 freopen("in.txt", "r", stdin);
87 freopen("out.txt", "w+", stdout);
88 #endif
89 while (tree.gogo());
90 return 0;
91 }
View Code
