Problem Description
已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历和层序遍历。
Input
输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的先序遍历序列，第二个字符串表示二叉树的中序遍历序列。
Output
每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列。
Sample Input
2
abdegcf
dbgeafc
xnliu
lnixu
Sample Output
dgebfca
abcdefg
linux
xnuli
/** By Mercury_LC */
/** https://blog.csdn.net/Mercury_Lc */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
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;
}
}
}
void postorder_traversal(struct node *root) // 后序遍历，顺序：左子树-右子树-根
{
if(root)
{
postorder_traversal(root->lc);
postorder_traversal(root->rc);
printf("%c",root->data);
}
}
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);
postorder_traversal(root);
printf("n");
level_traversal(root);
printf("n");
}
return 0;
}
