算法题来自hihocoder
你可以在我的github获取源码
题目要求使用树的前序遍历和中序遍历求出树的后序遍历串。那么我们想到的方法便是根据前序遍历和中序遍历求出这棵树，那么就可以很容易的后序遍历此树了。
根据题目我们先来定义树节点的数据结构：
typedef struct node{
char c;
struct node *left;
struct node *right;
} node_t;
那么我们可以这样设定这个函数：
//str1 为前序遍历串, str2 为中序遍历串 返回这棵树的根
node_t* tree(const char *str1,const char *str2)
我们可以根据树的定义：
前序遍历=root + 左子树前序遍历 + 右子树前序遍历
中序遍历=左子树中序遍历 + root + 右子树中序遍历
可以知道树的根节点root就是字串的第一个字符str1[0], 而根据这个根节点我们可以从str2中找到这个root节点，那么str2中在root节点左边的字符串str2l就是这棵树的左子树中序遍历结果，而这 个左子树的节点个数（即str2l字符串长度）n就可以得到了，从而在str1中可以取得左子树的前序遍历遍历结果：即str[1]到str[1+n]这 个便是左子树的前序遍历结果。
得到了左子树的前序遍历和左子树的中序遍历，那么我们又可以很开心的使用我们tree（）函数了，这就返回的 是左子树，连接到我们node->left就完成了左子树的构造。右子树使用相同的方法就可以得到一棵完整的树。那么接下就后序遍历这棵树打印答案 吧，enjoy it。
完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node{
char c;
struct node *left;
struct node *right;
}node_t;
node_t* tree(const char *str1,const char *str2)
{
int len = strlen(str1);
if(len == 0)
return NULL;
node_t *node = (node_t*)malloc(sizeof(node_t));
node->c = str1[0];
char lpre[30];
char lmid[30];
memset(lpre,0,30);
memset(lmid,0,30);
int count=0;
while(str2[count] != str1[0])
count++;
strncpy(lpre,str1+1,count);
strncpy(lmid,str2,count);
node->left = tree(lpre,lmid);
char rpre[30];
char rmid[30];
memset(rpre,0,30);
memset(rmid,0,30);
strncpy(rpre,str1+1+count,len-count-1);
strncpy(rmid,str2+count+1,len-count-1);
node->right = tree(rpre,rmid);
return node;
}
void ans(node_t *node)
{
if(node->left != NULL)
ans(node->left);
if(node->right != NULL)
ans(node->right);
printf("%c",node->c);
}
int main()
{
node_t *root;
char str1[30];
char str2[30];
scanf("%s%s",str1,str2);
root = tree(str1,str2);
ans(root);
return 0;
}
