UVa 548 - Tree 二叉樹的重建——中序遍歷與後續遍歷進行建樹

題目大意：
給兩個組數字，都是在同一棵二叉樹上的，第一組是按中序遍歷（inorder）順序輸出的，第二組是按後序遍歷（postorder）輸出的， 根據這兩組數據構建出原來的二叉樹，然後計算從根結點到每個葉子結點的路徑上的數字之和， 輸出最小之和。

樣例輸入：
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

樣例輸出：
1
3
255

分析：
這題就是運用了二叉樹重建， 以及遍歷。
二叉樹的遍歷：先序遍歷，中序遍歷，後序遍歷
只要有一個中序序列再加上另一個序列就可唯一地重建原來二叉樹。
進行了二叉樹重建之後，只要對這棵二叉樹進行搜索， 取得各個路徑之和，然後找出最小的那個和即可。

由中序遍歷 分別和前序遍歷，後序遍歷進行建樹的方法：
[cpp] 
// 由中序和後序遍歷序列進行建樹， 返回根結點指針 
Node * InPostCreateTree(int *mid,int *post,int len){ 
    if(len == 0) 
        return NULL; 
    int i=len-1; 
    while(post[len-1] != mid[i]) 
        --i; 
    Node *h=NewNode(); 
    h->data=post[len-1]; 
    h->left=InPostCreateTree(mid,post,i); 
    h->right=InPostCreateTree(mid+i+1,post+i,len-i-1); 
    return h; 
} 
  
// 由前序和中序遍歷序列進行建樹， 返回根結點的指針 
Node * PreInCreateTree(int *mid,int *pre,int len)   //n標識s2的長度 
{  
    if(len==0) 
        return NULL; 
     
    int i = 0; 
    while(*mid != pre[i]) 
    ++i; 
 
    Node *h=NewNode(); 
    h->data= *mid; 
    h->left  = PreInCreateTree(mid+1, pre, i); 
    h->right = PreInCreateTree(mid+i+1, pre+i+1, len-i-1); 
    return h; 
} 

AC代碼：
[cpp]
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<vector> 
using namespace std; 
const int MAXN = 10005; 
int inOrder[MAXN], postOrder[MAXN], nIndex; 
 
class Node{ 
public: 
    int data; 
    Node *left; 
    Node *right; 
}; 
 
int nodeIndex; 
Node node[MAXN]; 
vector<int>result; 
vector<Node*>pResult; 
bool flag; 
int ans; 
 
inline Node* NewNode(){ 
    node[nodeIndex].left = NULL; 
    node[nodeIndex].right = NULL; 
    return &node[nodeIndex++]; 
} 
  
inline void input(){ 
    nIndex=1; 
    while(getchar()!='\n')  
        scanf("%d", &inOrder[nIndex++]); 
    // 輸入第二行，後序遍歷 
    for(int i=0; i<nIndex; ++i)  
        scanf("%d", &postOrder[i]); 
}  
 
// 由中序和後序遍歷序列進行建樹， 返回根結點指針 
Node * InPostCreateTree(int *mid,int *post,int len){ 
    if(len == 0) 
        return NULL; 
    int i=len-1; 
    while(post[len-1] != mid[i]) 
        --i; 
    Node *h=NewNode(); 
    h->data=post[len-1]; 
    h->left=InPostCreateTree(mid,post,i); 
    h->right=InPostCreateTree(mid+i+1,post+i,len-i-1); 
    return h; 
} 
 
void dfs(Node *root, int n){ 
    if(!root->left && !root->right){ 
        result.push_back(n+root->data); 
        pResult.push_back(root); 
        return ; 
    } 
    if(root->left) dfs(root->left, n+root->data); 
    if(root->right) dfs(root->right, n+root->data); 
} 
 
int main(){ 
    freopen("input.txt","r",stdin); 
    while(~scanf("%d", &inOrder[0])){ 
        input(); 
        nodeIndex = 0; 
        Node *root = InPostCreateTree(inOrder, postOrder, nIndex); 
        result.clear(); 
        pResult.clear(); 
        dfs(root, 0); 
        int minPos = 0; 
        for(int i=1; i<result.size(); ++i) 
            if(result[i] < result[minPos]) minPos=i; 
         
        printf("%d\n",pResult[minPos]->data); 
    }   
    return 0; 
}