二叉樹已知前序，中序，求後序

今天上課時偶爾看到網易的面試題，二十四個選擇題做了一個多小時隻做對八個，菜的一筆。其中有一道二叉樹已知前序中序求後序的題我想拿出來寫一下解題思路。

首先明确什麼是前序中序後序周遊。

前序：首先通路根節點，然後遞歸前序周遊左子樹，再遞歸前序周遊右子樹

中序：首先遞歸前序周遊左子樹，通路根節點，然後遞歸前序周遊右子樹

後序：首先遞歸後序周遊左子樹，然後遞歸後序周遊右子樹，然後通路根節點

那麼，已知前序為GDAFEMHZ，中序為ADEFGHMZ，求後序。

由前序性質可知，整個樹的根節點是G,又由中序可知，ADEF是G的左子樹，MHZ是G的右子樹。由前序可知，通路完根節點之後就通路左子節點，該過程是遞歸的，是以D是左子樹的根節點，M是右子樹的根節點。遞歸過程，最後可以推出來整棵樹。

那麼以上可以分為以下幾個步驟：

确定根，确定左子樹，确定右子樹

在左子樹中遞歸以上過程

在右子樹中遞歸以上過程

列印目前根

寫了一段c++代碼來自動搞這些步驟，最後可以看到輸出的後序AEFDHZMG

using namespace std;

struct TreeNode {
    string elem;
};

//第三個參數是左右子樹的長度
void BinaryTreeFromOrderings(string inorder, string preorder, unsigned int length) {
    if (length == ) {
        return;
    }
    TreeNode *node = new TreeNode;
    node->elem = preorder;
    unsigned int rootIndex = ;
    for (; rootIndex < length; rootIndex++) {
        if (inorder[rootIndex] == preorder[]) {//此時
            break;
        }

    }
    //Left的inorder(中序)按照原樣傳進去即可，因為另外一個參數rootIndex會限制它
    BinaryTreeFromOrderings(inorder, preorder.substr(), rootIndex);
    //Right，這個函數傳參的寫法還是比較能夠考察對樹的了解的
    BinaryTreeFromOrderings(inorder.substr(rootIndex + ), preorder.substr(rootIndex + ), length - (rootIndex + ));
    cout << node->elem[] << endl;
    return;
}


int main(int argc, char *argv[]) {
    string pr = "GDAFEMHZ";
    string in = "ADEFGHMZ";
    BinaryTreeFromOrderings(in, pr, pr.size());
    return ;
}