【遞歸】中序-後序構造二叉樹

中南大學在2019年算法題部分考察了由先序與中序構造二叉樹算法，本文出于備考角度，将給出依靠遞歸算法由中序與後序序列構造二叉樹過程，本算法隻涉及核心代碼（C++），其餘考完補充。

struct node{
        int data;           //資料域
        node *left;         //左孩子
        node *right;        //右孩子
};
int in[max],post[max];

//目前二叉樹周遊的後序周遊區間為[postL,postR],中序周遊區間為[inL,inR]
//由create函數傳回建構出的二叉樹的根節點位址

node *create(int postL,int postR,int inL,int inR){
    if( postL > postR ) return Null;  //區間越界
    node *root = new node();          //建立新節點（根）
    root->data = post[postR];         //新節點資料域為根節點的值
    int cur;    
    for(cur=inL; cur<=inR; cur++){    //周遊确定根節點及左右子樹區間
        if(in[cur] == post[postR]) break;
    }
    int numLeft=cur-inL;              //左子樹中根節點個數
    root->left = create(postL,postL+numLeft-1,inL,cur-1);//遞歸左子樹
    root->right = create(postL+numLeft,postR,cur+1,inR); //遞歸右子樹
    return root;                      //傳回建構出的二叉樹的根節點位址
}