问题描述： 输入显示的是中序遍历非递归，栈的操作，输出树的后序遍历 问题关键 push的顺序为先序遍历，pop的顺序为中序遍历 问题转换为由先序遍历、中序遍历求后续遍历
/*=============================================================================#COPYRIGHT NOTICE#Copyright (c) 2015##@Author:TonyChou#@Email:whzyb1991@163.com#@Filename:/home/zhoudaxia/program/PAT_MOOC_DS\03_3.cc#@Last modified:2015-06-30 21:22#@Description :=============================================================================*/;int find_head(vector<int> &v, int data){for(int i = 0; i!= v.size(); ++i)if(v[i]==data)return i;}void find_post(vector<int> &v1, vector<int> &v2,int left2, int right2, int head1){int head2 = find_head(v2, v1[head1]);int left_size = head2 – left2;if(head1!=v1.size()){if(head2>left2)find_post(v1,v2,left2, head2-1, head1+1);if(head2<right2)find_post(v1,v2,head2+1,right2,head1+left_size+1);if(head1==0)cout << v1[head1];elsecout << v1[head1] <<” “;}}int main(){int N;string s;int node;vector<int> pre_v;vector<int> in_v;stack<int> sta;cin >> N;for(int i=0;i != 2*N; ++i){cin >> s;if(s==”Push”){cin>>node;pre_v.push_back(node);sta.push(node);}else{in_v.push_back(sta.top());sta.pop();}}find_post(pre_v,in_v,0,pre_v.size()-1,0);return 0;}
解析 先序遍历在v1中 1 2 3 4 5 6 后序遍历 3 2 4 1 6 5
递归中的参数【left2 right2】为左子树的在v2的范围，head1为头结点在v1的位置 head2为头结点在v2的位置 递归的出口是head1遍历到v1尾部, 当head2！=left2时递归[left2,head2-1] head2 != right2时递归[head2+1,right2] 否则输出v1[head1]
，所有的赏赐都只是被用来奖励工作成果的。
