描述
题目很简单，给你一棵二叉树的后序和中序序列，求出它的前序序列（So easy!）。
- 输入
输入有多组数据（少于100组），以文件结尾结束。每组数据仅一行，包括两个字符串，中间用空格隔开，分别表示二叉树的后序和中序序列（字符串长度小于26，输入数据保证合法）。 - 输出
每组输出数据单独占一行，输出对应得先序序列。 - 样例输入
ACBFGED ABCDEFG
CDAB CBAD - 样例输出
DBACEGF
BCAD
分析：
与树的遍历这道题基本上可以说是一毛一样了，唯一的不同就是这道题是已知一棵二叉树的后序和中序序列，让输出该棵二叉树的先序序列；而树的遍历那道题是已知一颗二叉树的先序和中序序列，要求输出该棵二叉树的后序序列。换汤不换药，代码只需略加改动。
代码：
#include<string>
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct Node
{
char data;
Node * lchild;
Node * rchild;
};
Node *build(string hou,string in)
{
Node * root=NULL;
if(hou.length()>0)
{
int k=hou.length();
root=new Node;
root->data=hou[k-1];
int index=in.find(hou[k-1]);///在中序序列中找到当前树的根节点
root->lchild=build(hou.substr(0,index),in.substr(0,index));///递归左子树
root->rchild=build(hou.substr(index,k-1-index),in.substr(index+1));///递归右子树
}
return root;
}
void post(Node *root)
{
if(root!=NULL)
{
printf("%c",root->data);///先输出根节点
post(root->lchild);///再访问左子树
post(root->rchild);///最后访问右子树
}
}
int main()
{
string hou,in;
while(cin>>hou>>in)
{
Node* root=build(hou,in);///将后序和中序序列转换为先序序列
post(root);///先序序列递归输出
cout<<endl;
}
return 0;
}