Time Limit: 1000MS  Memory Limit: 65536KB
Submit  Statistic  Discuss

Problem Description

 已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历

Input

 输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的中序遍历序列，第二个字符串表示二叉树的后序遍历序列。 

Output

 输出二叉树的先序遍历序列

Example Input

2
dbgeafc
dgebfca
lnixu
linux

Example Output

abdegcf
xnliu

Hint

  
#include<bits/stdc++.h> using namespace std; struct node { char data; struct node *l, *r; }; typedef struct node Bintree; Bintree *Creat(int n, char *a, char *b) { Bintree *root; root = new node; char *p; if(n<=0) return NULL; root->data = b[n-1]; for(p = a; p; p++) { if(*p == root->data) break; } int t; t = p-a; root->l = Creat(t,a,b); root->r = Creat(n-t-1,p+1,b+t); return root; } void qian(Bintree *root) { if(root) { printf("%c", root->data); qian(root->l); qian(root->r); } } int main() { int t; scanf("%d", &t); while(t--) { Bintree *root; root = new node; char a[10000], b[10000]; int n; cin>>a; cin>>b; n = strlen(a); root = Creat(n,a, b); qian(root); printf("\n"); } return 0; }