# 前中序建立二元樹

>有一個包含N個節點的二元樹，其中有節點1~N（數字不會重複），給定前序和中序走訪的結果，請求出這棵二元樹後序走訪的結果。

## 唯一性證明
首先我們先證明，給定一棵二元樹的前序與中序走訪，可以決定出唯一的二元樹
整個證明是利用數學歸納法來進行證明，架構如下:
>當N=1時，命題顯然成立。
>設N<=k時命題成立。
>證明N=k+1時命題成立。

由於N=1時命題顯然成立，我們僅需證明在N<=k命題成立時，N=k+1也會成立即可。證明如下：

假設二元樹的前序序列為$\{a_1,a_2,a_3,...,a_N\}$，中序序列為$\{b_1,b_2,b_3,...,b_N\}$
令與$a_1$相同的元素為$b_j$，則可以分為以下三種情況：
1. j=1
根據中序走訪的定義，此時根節點沒有左子樹，$\{a_2,a_3,...,a_N\}$與$\{b_2,b_3,...,b_N\}$（N-1個節點）決定唯一的右子樹。
2. j=N
根據中序走訪的定義，此時根節點沒有右子樹。$\{a_2,a_3,...,a_N\}$與$\{b_1,b_2,...,b_{N-1}\}$(N-1個節點)決定唯一的左子樹

3. 2<=j<=N-1
根據中序走訪的定義，此時左子樹與右子樹的前、中序序列分別為:
$\{a_2,a_3,...,a_j\}$，$\{b_1,b_2,...,b_{j-1}\}$與
$\{a_{j+1},a_{j+2},...,a_N\}$，$\{b_{j+1},b_{j+2},...,b_N\}$
這兩者都是大小<N的子樹，故也會決定唯一的左子樹和右子樹

已知左子樹和右子樹唯一，根節點也已被決定，故得證其唯一性。

## 演算法
前中序求後序的重點在利用前序來求得樹根，再以中序來分開左右子樹，再遞迴求解即可。
程式碼如下：

#include<iostream>
#include<vector>
using namespace std;

void dac(vector<int> in,vector<int> pre){

    if(in.size()==0)return;
    if(in.size()==1){
        cout<<in[0]<<" ";
        return;
    }
    int root = pre[0];
    int rootIndexInin;//求根在中序的index
    for(int i = 0;i<in.size();i++){
        if(in[i]==root){
            rootIndexInin= i;
            break;
        }
    }

    
    vector<int> inL,inR,preL,preR;
    
    //分開左右子樹的中序序列
    for(int i = 0;i<rootIndexInin;i++){
        inL.push_back(in[i]);
    }
    for(int i = rootIndexInin+1;i<in.size();i++){
        inR.push_back(in[i]);
    }
    
    //分開左右子樹的前序序列
    for(int i = 1;i<inL.size()+1;i++){
        preL.push_back(pre[i]);
    }
    for(int i =inL.size()+1;i<pre.size();i++){
        preR.push_back(pre[i]);
    }

    dac(inL,preL);
    dac(inR,preR);
    cout<<root<<" ";
}

int main(){
    int n;
    cin>>n;
    vector<int> in,pre;
    in.resize(n);
    pre.resize(n);
    for(int &i:pre)cin>>i;
    for(int &i:in)cin>>i;

    dac(in,pre);

}

若是要改為建出二元樹，只要將輸出根的編號改為將左右子樹接到該根後，回傳根節點即可。

## 參考資料
https://blog.csdn.net/qq_34070321/article/details/84583830
HGOJ