KY212二叉树遍历

描述

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

输入描述：

两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出描述：

输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。 -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 解法如下：

#include
#include

char pre[26];
char in[26];
char post[26];

/**三个low和high分别是pre，in和post的起止位置*/
void Post(int low1,int high1,int low2,int high2,int low,int high)
{
    if(low>high) return ;
    char c=pre[low1];
    post[high]=c;   /**把pre[]第一个字符赋给post[]最后一个位置*/
    int k=0;
    while(in[low2+k]!=c)    /**找到pre[]第一个字符在in[]中的位置*/
        k++;
    Post(low1+1,low1+k,low2,low2+k-1,low,low+k-1);
    Post(low1+k+1,high1,low2+k+1,high2,low+k,high-1);
    return ;
}

int main()
{
    while(scanf("%s",pre)!=EOF)
    {
        scanf(" %s",in);
        int len=strlen(pre);
        Post(0,len-1,0,len-1,0,len-1);
        printf("%s",post);
        printf("\n");
    }
    return 0;
}