重建二叉树
时间限制： 1000 ms | 内存限制：65535 KB
难度： 3
- 描述
- 题目很简单，给你一棵二叉树的后序和中序序列，求出它的前序序列（So easy!）。
- 输入
- 输入有多组数据（少于100组），以文件结尾结束。 每组数据仅一行，包括两个字符串，中间用空格隔开，分别表示二叉树的后序和中序序列（字符串长度小于26，输入数据保证合法）。 输出
- 每组输出数据单独占一行，输出对应得先序序列。 样例输入
-
ACBFGED ABCDEFGCDAB CBAD
样例输出 -
DBACEGFBCAD
来源 - 题解：由中后序重建二叉树，再输出；
- 代码：
-
#include
#include #include #include #include #include using namespace std;struct Node{ Node *l, *r; char val; Node(){ l = r = NULL; }};int find(char *a , char x){ for(int i = 0; a[i]; i++){ if(x == a[i]){ //printf("i = %d\n", i); return i; } } return 0;}Node* build(int n, char *a, char *b){ if(n <= 0)return NULL; Node *x; x = new Node; x->val = b[n - 1]; int p = find(a, x->val); x->l = build(p, a, b); x->r = build(n - p - 1, a + find(a, x->val) + 1, b + p); return x;}void visit(Node *root){ if(root == NULL)return; printf("%c", root->val); visit(root->l); visit(root->r);}int main(){ char a[110], b[110]; while(~scanf("%s%s", b, a)){ Node *root = build(strlen(b), a, b); visit(root);puts(""); } return 0;} 其实也可以不建树，直接输出；
代码：
#include
#include #include #include #include #include using namespace std;/*struct Node{ Node *l, *r; char val; Node(){ l = r = NULL; }};int find(char *a , char x){ for(int i = 0; a[i]; i++){ if(x == a[i]){ //printf("i = %d\n", i); return i; } } return 0;}Node* build(int n, char *a, char *b){ if(n <= 0)return NULL; Node *x; x = new Node; x->val = b[n - 1]; int p = find(a, x->val); x->l = build(p, a, b); x->r = build(n - p - 1, a + find(a, x->val) + 1, b + p); return x;}void visit(Node *root){ if(root == NULL)return; printf("%c", root->val); visit(root->l); visit(root->r);}*/void dfs(int n, char *a, char *b){ if(n <= 0)return; printf("%c", b[n - 1]); int p = strchr(a, b[n - 1]) - a; dfs(p, a, b); dfs(n - p - 1, a + p + 1, b + p);}int main(){ char a[110], b[110]; while(~scanf("%s%s", b, a)){// Node *root = build(strlen(b), a, b);// visit(root);puts(""); dfs(strlen(b), a, b);puts(""); } return 0;}