九度oj 1385 重建二叉樹

原題地址：http://ac.jobdu.com/problem.php?pid=1385

題目描述：

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列 {1,2,4,7,3,5,6,8} 和中序遍歷序列 {4,7,2,1,5,3,8,6}，則重建二叉樹並輸出它的後序遍歷序列。

算法描述：

前序遍歷：根左右；中序遍歷：左根右；後序遍歷：左右根。

前序遍歷序列 {1,2,4,7,3,5,6,8} 中，前序序列中的第一個元素：1作為根將中序遍歷序列 {4,7,2,1,5,3,8,6} 分為兩部分，這兩部分分別對應前序遍歷序列中的兩部分。

即：子前序遍歷序列 {2, 4, 7} 和子中序遍歷序列 {4, 7, 2} 。然後迭代使用前序序列中的第一個元素作為分隔符將中序遍歷序列隔成兩個序列。

分成三個函數：主函數、midFind（找到前序序列第一個對應在中序序列的分隔位置）、post（主迭代函數）。

post 中如果出現的 left 和 right 分別代表子樹的范圍（前序、中序的子樹范圍大小關系是一致的），如果：

（1）left > right，則此子樹為空；（2）left == right，則此子樹僅有一個根節點；（3）left < right，繼續迭代。

注意：

這題最坑爹的地方，如果是（1）為空子樹則不用判斷；如果是（3）迭代時需要用 midFind 尋找判斷是否元素存在；但是如果是（2）僅有一個根節點時，我忘記比較前序的根節點與後序的根節點是否是同一元素，不是一個元素則說明前序、中序不是同一個二叉樹。

同時，再次迭代的順序一定不能錯，要記錄後序序列，所以 post 按照 left - right - root 順序引用。

#include 
#include 
#include 
#define MAX 1005

using namespace std;

int preArray[MAX];
int midArray[MAX];
int postArray[MAX];
int postIndex;

int midFind(int *array, int left, int right, int target)
{
    for(int i=left; i <= right; i++)
    {
        if(array[i] == target)
            return (i - left);
    }
    return MAX;                       // return MAX; means "end" 
}
    
int post(int preLeft, int preRight, int midLeft, int midRight)
{
    //  1. empty subtree  
    if(preLeft > preRight || midLeft > midRight)
        return 1;
    
    //  2. subtree is just a root node  
    if(preLeft == preRight || midLeft == midRight){
        if (preArray[preLeft] != midArray[midLeft])
            return 0;
        else{
            postArray[postIndex] = preArray[preLeft];
            postIndex ++;
            return 1;
        }
    }
     
    //  3. normal subtree   
    int midOffset = midFind(midArray, midLeft, midRight, preArray[preLeft]);
    if(midOffset == MAX)              // can't find the target 
    {
        return 0;
    }
    else
    {
        // 此處 if 順序一定不能錯，要記錄後序所以 post 按照 left - right - root 順序 
        if( post(preLeft + 1, preLeft+midOffset, midLeft, midLeft+midOffset - 1) && 
            post(preLeft+midOffset + 1, preRight, midLeft+midOffset + 1, midRight))
        {
            postArray[postIndex] = preArray[preLeft];
            postIndex ++;
            return 1;
        }
        else
            return 0;
    }
}

int main(){
    int n;
    while(scanf("%d", &n)==1)
    {
        memset(preArray, 0, MAX);
        memset(midArray, 0, MAX);
        memset(postArray, 0, MAX);
        postIndex = 0;
        
        for(int i=0; i