USACO Section 3.4 American Heritage - 知道前序遍历与中序遍历求后序遍历

这道题主要就是要抓住前序遍历和中序遍历的特点...前序便利是(自己,左孩子,右孩子)..中序便利是(左孩子,自己,右孩子)...而要求的后序遍历是(左孩子,右孩子,自己)..

若是在中序遍历从左到右的顺序中..先跳过中间的自己...后面某个位置再把自己计回来..那应该能得到后序遍历...而在前序遍历中一个点的孩子肯定在其右边...所以两者结合起来一起直接就推出后序遍历..

这里用一个栈来维护...从中序遍历的最左边开始往最右边扫描..若当前点x=in_order[i]与后面的点y=in_order[i+1]在前序便利中..y在x的左边代表y是x的父亲..那么暂时不输出..放到栈顶...反之则说明x没有孩子了..直接输出x...什么时候弹栈..这里也比较好想...在做x,y判断之前先判断x是否在前序遍历中在栈顶点的左边...是的话就弹栈..(while循环判断操作)..

Program:

/* ID: zzyzzy12 LANG: C++ TASK: heritage */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long using namespace std; char in_order[30],pre_order[30],post_order[30]; int s[30],i,l; stack<char> mystack; int main() { freopen("heritage.in","r",stdin); freopen("heritage.out","w",stdout); gets(in_order); gets(pre_order); l=strlen(pre_order); for (i=0;i<l;i++) s[pre_order[i]-'A']=i; while (!mystack.empty()) mystack.pop(); for (i=0;i<l;i++) { while (!mystack.empty() && s[mystack.top()-'A']>s[in_order[i]-'A']) { printf("%c",mystack.top()); mystack.pop(); } if (s[in_order[i]-'A']>s[in_order[i+1]-'A']) printf("%c",in_order[i]); else mystack.push(in_order[i]); } while (!mystack.empty()) { printf("%c",mystack.top()); mystack.pop(); } printf("\n"); return 0; }