7 4 2 8 9 5 6 3 1
由二叉树的前序遍历和中序遍历，求后序遍历
大概思路就是：在中序里找前序第一个pre[0]，找到的位置i即为根节点，那么中序里[0,i-1]即是左子树，[i+1,n-1]即为右子树（n为中序序列的长度，下标从0开始的），同时前序的第一个元素（即根节点）就没用了，因为根节点已经构造出来了，那么就从pre[1]开始把前序序列pre分成两部分，怎么分呢？就是前半部分的长度和[0,i-1]长度相等，后半部分和[i+1,l-1]长度相等，然后这就有了两对分半的前序序列和后序序列，然后用这两对分别左右递归构造左右子树。
注意：每次分的前序和中序序列都必须保证长度相等！
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <algorithm>using namespace std;int pre[1100],mid[1100],n;typedef struct Node{int v;struct Node *left,*right;}node;node* root;node* newNode(int x){node* u=(node*)malloc(sizeof(node));u->left=u->right=NULL;u->v=x;return u;}node* creat(int *pre,int l1,int *mid,int l2){int i,j,k;for(i=0;i<l2;i++)if(pre[0]==mid[i]) break;node* u=newNode(mid[i]);if(i>0)u->left=creat(pre+1,i,mid,i);//重点理解这两个if就好了if(i<l2-1)u->right=creat(pre+i+1,l2-i-1,mid+i+1,l2-i-1);return u;}void remove_tree(node* u){if(u==NULL) return ;remove_tree(u->left);remove_tree(u->right);delete u;}int f;void print(node* u){if(u==NULL) return ;print(u->left);print(u->right);if(f)printf(" ");f=1;printf("%d",u->v);}int main(){int i,j,n;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&pre[i]);for(i=0;i<n;i++)scanf("%d",&mid[i]);remove_tree(root);root=creat(pre,n,mid,n);f=0;print(root);printf("\n");}return 0;}
注意要养成释放空间的好习惯！
POJ2255和这个题基本一样
POJ2255
，最有效的资本是我们的信誉，它24小时不停为我们工作。
