hihoCoder week10-1-后序遍历 题目1 : 后序遍历 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在参与过了美食节之后，小Hi和小Ho在别的地方又玩耍了一阵子，在这个过程中，小Ho得到了一个非常有意思的玩具——一棵由小球和木棍连接起来的二叉树！ 小Ho对这棵二叉树爱不释手，于是给它的每一个节点都标记了一个标号——一个属于A..Z的大写字母，并且没有任意两个节点的标号是一样的。小Hi也瞅准了这个机会，重新巩固了一下小Ho关于二叉树遍历的基础知识~就这样，日子安稳的过了两天。 这天，小Ho正好在求解这棵二叉树的前序、中序和后序遍历的结果，但是却在求出前序遍历和中序遍历之后不小心把二叉树摔到了地上，小球和木棍等零件散落了一地！ 小Ho损失了心爱的玩具，正要嚎啕大哭起来，所幸被小Hi发现了，劝说道：“别着急，这不是零件都还在么？拼起来不就是了？” “可是我忘记了二叉树长什么样子了！”小Ho沮丧道。 “这个简单，你不是刚刚求出了这棵二叉树的前序和中序遍历的结果么，利用这两个信息就可以还原出整棵二叉树来哦！” “这样么？！！”小Ho止住了泪水，问道：“那要怎么做呢？” 没错！小Ho在这一周遇到的问题便是：给出一棵二叉树的前序和中序遍历的结果，还原这棵二叉树并输出其后序遍历的结果。 提示：分而治之——化大为小，化小为无 输入 每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第一行为一个由大写英文字母组成的字符串，表示该二叉树的前序遍历的结果。 每组测试数据的第二行为一个由大写英文字母组成的字符串，表示该二叉树的中序遍历的结果。 对于100%的数据，满足二叉树的节点数小于等于26。 输出 对于每组测试数据，输出一个由大写英文字母组成的字符串，表示还原出的二叉树的后序遍历的结果。 样例输入 AB BA 样例输出 BA

---

解法一（已更新简洁版解法二） 简单来说就是根据前序遍历和中序遍历的结果求得后序遍历。这个题目如果用手算的话还简单些，但是要用程序实现，还真让我无从下手。不过可以明确的思路是：依次取前序遍历中的一个元素，找它在中序遍历中的位置，然后把中序遍历分成左右两部分，再在左右两部分递归求解。 递归的思路虽然简单，具体代码实现时有很多细节需要注意，我参考了这篇博文里面的用前序遍历和中序遍历重建二叉树的代码。但是代码好像有一点小问题，指针横飞，我根据《数据结构》P161整理如下： [cpp] #include<iostream> #include<string> #include<cstdlib> using namespace std; typedef struct node_t { char data; struct node_t* lchild; struct node_t* rchild; }node;//树的定义 //根据先序遍历和中序遍历还原树结构 void rebuild_tree_from_pre_in_order(string &pre_order,string in_order,int tree_len,node*& root)//注意node*&要带上&，表示node*root的引用，看数据结构P162 { if(pre_order==""||in_order=="") return; node *tmp=(node*)malloc(sizeof(node)); tmp->data=pre_order[0]; tmp->lchild=NULL; tmp->rchild=NULL; if(root==NULL) root=tmp;//这里改变了root指针的指向，所以传进来的时候要node*& root使用引用！ if(tree_len==1) { pre_order=pre_order.substr(1); //每次取前序遍历的元素之后都要将其删除，并且要将结果带出去 return; } int i=0,left_len=0,right_len=0; while(pre_order[0]!=in_order[i])//找到先序遍历中的根在中序遍历中的位置，将中序遍历一分为二 i++; left_len=i; right_len=in_order.size()-i-1; pre_order=pre_order.substr(1);//每次取先序遍历的元素之后都要将其删除，如果tree_len!=1，则要先计算了left_len和right_len之后再删除 if(left_len>0) rebuild_tree_from_pre_in_order(pre_order,in_order.substr(0,left_len),left_len,root->lchild);//递归左子树 if(right_len>0) rebuild_tree_from_pre_in_order(pre_order,in_order.substr(i+1,right_len),right_len,root->rchild);//递归右子树 } //后序遍历 void post_order_print(node* root) { if(root!=NULL) { post_order_print(root->lchild); post_order_print(root->rchild); cout<<root->data; } } int main() { string pre_order,in_order; cin>>pre_order>>in_order; node* root=NULL; rebuild_tree_from_pre_in_order(pre_order,in_order,pre_order.size(),root); post_order_print(root); return 0; } [/cpp] 首先利用递归的思想重建二叉树，然后后序遍历输出。需要注意的是我把二叉树节点统一定义为node，重建函数 [cpp] void rebuild_tree_from_pre_in_order(string &pre_order,string in_order,int tree_len,node*& root) [/cpp] 传入的参数需要写成node*& root，也就是node* root指针的引用，如果是C语言里可以用二级指针，因为在这个函数内部对指针node* root进行了修改（if(root==NULL) root=tmp;），也就是改变了上一个node里的 node_t* lchild和node_t* rchild的指向，这是改变了指针的指向（指针本身的内容），所以需要传入指针的引用，如果只是想改变指针指向的内容node->data，可以只用node*，总之一句话，想改变什么就传入什么的指针，想改变int就传入int*或者int&，想改变node*就传入node**或者node*&，这个在链表里也有类似的应用。 还有一个通俗易懂的例子： [cpp] #include<stdio.h> #include<stdlib.h> #include<string.h> void get_memory(char*& buffer,int n) { buffer=(char*)malloc(sizeof(char)*n); } int main() { char *str=NULL; get_memory(str,20); strcpy(str,"Hello World!"); printf("%s",str); return 0; } [/cpp] 如果void get_memory(char*& buffer,int n);的形参buffer不是传入指针的引用的话，函数里malloc分配的内存只是分配给了char*的副本，并不会传出去，这样会导致内存泄露。 解法二（2015.4.16更新） 今天回头来看解法一真是笨拙，解法一先恢复了树的结构，然后求树的后序遍历。其实可以不用这么复杂，题目的提示已经很明确了，不知道当时为什么没有注意到。 具体解法是这样的，假设s,t分别为前序遍历和中序遍历，则s=根+左+右；t=左+根+右；根据s可以知道根节点，在t中查找根节点，可以把t分成左和右，因为s和t的左右孩子长度是一样的，所以也可以把s分成左和右。这样我们就分别有了左孩子和右孩子的前序和中序遍历，又可以递归上述过程。 通过这种方法，我们可以由前序和中序遍历直接得到后序遍历。具体代码如下： [cpp] #include<iostream> #include<string> using namespace std; //s前序，t中序 string get_post_order(string s,string t) { if(s=="") return ""; if(s.size()==1) return s; int i; for(i=0;i<t.size();i++) if(t[i]==s[0]) break; string s_left=s.substr(1,i); string s_right=s.substr(i+1);//如果i+1==长度，则返回空串，当i+1>长度时才抛出异常。 string t_left=t.substr(0,i); string t_right=t.substr(i+1); return get_post_order(s_left,t_left)+get_post_order(s_right,t_right)+s[0]; } int main() { string s,t; while(cin>>s>>t) cout<<get_post_order(s,t)<<endl; return 0; } [/cpp] 由于题目已经过期，没办法提交到hiho，我简单测试了几个例子，得到了正确的结果。]]>