hdu 1710 二叉樹遍歷

/*
二叉樹的遍歷：
先序遍歷(preorder traversal)：先遍歷父節點，然後是左孩子，右孩子。
中序遍歷(inorder traversal)：先遍歷左孩子，然後是父節點，最後遍歷右孩子。
後序遍歷(postorder traversal)：先遍歷左孩子和右孩子，然後遍歷父節點。
*/
題目大意：給出一個二叉樹的先序和中序遍歷序列，求後序遍歷序列；
思路：將一棵二叉樹分為根節點，左子樹，右子樹三部分。先讓根節點入棧，然後遞歸處理右子樹和左子樹(必須先右後左)。最後依次出棧即得到後序遍歷序列。
PS：本題解法是在假設所有節點數字不同的條件下進行的，題目並沒有給出這個條件，不過能過測試。

[cpp]
#include<iostream>  
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<stack>  
using namespace std; 
const int N=1005; 
int preorder[N],inorder[N]; 
stack<int>postorder; 
//二叉樹由先序序列和中序序列求後序序列  
void getpost(int pstart,int pend,int istart,int iend) 
{ 
    int i,j; 
    postorder.push(preorder[pstart]); 
 
    for(i=0;i<=iend;i++){  //i表示根節點在中序的位置  
        if(inorder[i]==preorder[pstart]) break; 
    } 
    j=pstart+(i-istart)+1; //j表示先序中左右子樹的分界點  
 
    if(j<=pend && i+1<=iend){  //求解右子樹  
        getpost(j,pend,i+1,iend); 
    } 
    if(pstart+1<=j-1 && istart<=i-1){  //求解左子樹  
        getpost(pstart+1,j-1,istart,i-1); 
    } 
} 
int main() 
{ 
    int i,n; 
    while(scanf("%d",&n)!=EOF){ 
        for(i=0;i<n;i++) scanf("%d",&preorder[i]); 
        for(i=0;i<n;i++) scanf("%d",&inorder[i]); 
        getpost(0,n-1,0,n-1); 
        while(!postorder.empty()){ 
            printf("%d",postorder.top()); 
            postorder.pop(); 
            if(!postorder.empty()) 
                printf(" "); 
        } 
        printf("\n"); 
    } 
    return 0; 
}