Problem Description

已知一颗二叉树的前序遍历和中序遍历，求二叉树的层次遍历。

---

Input

输入数据有多组，输入T，代表有T组测试数据。每组数据有两个长度小于50的字符串，第一个字符串为前序遍历，第二个为中序遍历。

---

Output

每组输出这颗二叉树的层次遍历。

---

Sample Input

2

abc

bac

abdec

dbeac

---

Sample Output

2

abc

bac

abdec

dbeac

/** By Mercury_LC *//** https://blog.csdn.net/Mercury_Lc */#include 
    
     #include 
     
      #include 
      
       struct node{    char data;  // 储存字符    struct node *lc, *rc;   // 左右节点};char preorder[100]; // 前序char inorder[100];  // 中序struct node *creat(int len, char *preorder, char *inorder)  /* 根据前序中序建立二叉树*/{    struct node *root;    int i;    if(len == 0) return NULL;   // 如果长度为零，则不能建树    root = (struct node*)malloc(sizeof(struct node));  // 申请新的节点    root -> data = preorder[0];  // 前序的顺序第一个一定是根节点    for(i = 0; i < len; i ++)  // 寻找中序中到根节点，即现在的这颗树的所有左子树    {        if(inorder[i] == preorder[0])break;  // 找到跳出循环    }    root -> lc = creat(i, preorder + 1, inorder);  // 建左子树    root -> rc = creat(len - i - 1, preorder + i + 1, inorder + i + 1); // 建右子树    return root;  // 返回根节点。};void level_traversal(struct node *root)  /* 层次遍历*/{    if(root == NULL) return;   // 树不存在    struct node *queue[10005], *now;  // 建立队列    int front = 0;   // 队首、尾初始化    int rear = 0;    queue[rear ++] = root;  // 入队    while(front < rear)    {        now = queue[front ++]; // 出队        printf("%c", now -> data);        if(now -> lc != NULL)  // 左子树        {            queue[rear++] = now -> lc;        }        if(now -> rc != NULL)  // 右子树        {            queue[rear++] = now -> rc;        }    }}int main(){    int t;    scanf("%d", &t);    while(t--)    {        scanf("%s%s",preorder,inorder);        struct node *root;        int len = strlen(preorder);        root = creat(len,preorder,inorder);        level_traversal(root);        printf("\n");    }    return 0;}