刚刚那种解法（传统的基于NODE重建树），我相信大部分人都没有任何困难。OK，在说新解法之前，先细细的品味一下前、中、后序遍历的特点。
1、前序遍历第一个节点一定是根节点。
2、后序遍历的最后一个节点一定是根节点。
3、根节点把中序遍历分成左子树和右子树。
好了，不就是求后序遍历么？为什么要建一个树呢？为什么，我也不知道为什么，惯性思维吧~下面我们根据这三者的特点直接对字符串操作。当然还是要用到递归调用，本身的实质还是树嘛！每次把根节点（也就是前序遍历字符串中的第一个节点）放在后序遍历字符串的最后，然后递归的重建左子树和右子树就可以了。OK，整个世界清静了~~
下面说说strchr(const char* str, const char ch)这个函数，也就是在str中找ch，找到了，就返回该字符的指针，否则返回NULL。
[cpp]
#include
#include
void Rebuild(const char *PreStr, const char *InStr, char *PostStr, int nLen)
{
if(nLen <= 0)
return;
int n = strchr(InStr, PreStr[0]) - InStr;
Rebuild(PreStr + 1, InStr, PostStr, n);
Rebuild(PreStr + n + 1, InStr + n + 1, PostStr + n, nLen - n - 1);
PostStr[nLen - 1] = PreStr[0];
}
int main()
{
char PreStr[27];
char InStr[27];
char PostStr[27];
int nLen;
while(scanf("%s %s", PreStr, InStr) != EOF)
{
nLen = strlen(PreStr);
Rebuild(PreStr, InStr, PostStr, nLen);
PostStr[nLen] = '\0';
puts(PostStr);
}
return 0;
}
#include
#include
void Rebuild(const char *PreStr, const char *InStr, char *PostStr, int nLen)
{
if(nLen <= 0)
return;
int n = strchr(InStr, PreStr[0]) - InStr;
Rebuild(PreStr + 1, InStr, PostStr, n);
Rebuild(PreStr + n + 1, InStr + n + 1, PostStr + n, nLen - n - 1);
PostStr[nLen - 1] = PreStr[0];
}
int main()
{
char PreStr[27];
char InStr[27];
char PostStr[27];
int nLen;
while(scanf("%s %s", PreStr, InStr) != EOF)
{
nLen = strlen(PreStr);
Rebuild(PreStr, InStr, PostStr, nLen);
PostStr[nLen] = '\0';
puts(PostStr);
}
return 0;
}