求二叉树的先序遍历
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
已知一棵二叉树的中序遍历和后序遍历,求二叉树的先序遍历
Input
输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括两个长度小于50 的字符串,第一个字符串表示二叉树的中序遍历序列,第二个字符串表示二叉树的后序遍历序列。
Output
输出二叉树的先序遍历序列
Sample Input
2
dbgeafc
dgebfca
lnixu
linux
Sample Output
abdegcf
xnliu
Hint
Source
GYX
#include <iostream>
//#include <string>
//#include <typeinfo>
//#include <algorithm>
#include <cstring>
using namespace std;
typedef struct nd
{
char data;
nd *left, *right;
} node, *pnode;
pnode zhonghou(char hou[],int len,char zhong[])
{
if(len<=0)
return NULL;
pnode root = nullptr;
root=new node();
root->data=hou[len-1];
int p;//根的下标
for(p=0; p<len; p++)
if(zhong[p]==hou[len-1])
break;
root->left=zhonghou(hou,p,zhong);
root->right=zhonghou(hou+p,len-p-1,zhong+p+1);
return root;
};
void xian(pnode root)
{
if(root)
{
cout << root->data;
xian(root->left);
xian(root->right);
}
}
int main()
{
int t;
char zhong[1000],hou[1000];
pnode root = nullptr;
cin >>t;
while(t--)
{
cin >> zhong >> hou;
int len =strlen(zhong);
root=zhonghou(hou,len,zhong);
xian(root);
cout << endl;
}
return 0;
}
还没有评论,来说两句吧...