根據先序中序還原二叉樹

先序周遊：根 —> 左 —> 右

中序周遊：左 —> 根 —> 右

後序周遊：左 —> 右 —>根

算法思想：

1. 根據先序周遊的特點，第一個周遊的結點就是根結點，我們找到根結點
2. 根據中序周遊的特點，我們知道此根結點左邊的序列為左子樹，根結點右側的序列為右子樹
3. 根據原始的先序和中序周遊結果，得到左右子樹的先序和中序周遊結果，遞歸還原二叉樹

根據周遊結果構造子樹的周遊結果：

• 後序周遊：[ [ 左子樹後序周遊結果 ]，[ 右子樹後序周遊結果 ]，根節點]
• 中序周遊：[[ 左子樹中序周遊結果 ]，根節點，[ 右子樹中序周遊結果 ]]

舉例：

preorder = [3,9,20,15,7]

inorder = [9,3,15,20,7]

首先我們根據preorder知道結點3為整個樹的根結點，然後根據inorder序列知道3左側的序列[9]為左子樹，右側的序列[15,20,7]為右子樹，就像這樣

接下來我們構造左右子樹的先序和中序周遊序列：

left_preorder = [9]

right_preorder = [20,15,7]

left_inorder = [9]

right_inorder = [15,20,7]

接下來就是遞歸的過程了。按照同樣的步驟，根據preorder序列的第一個元素得到根結點，根據得到的這個根結點以及inorder得到左右子樹，就像這樣：

代碼如下：

* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(inorder.size() == 0){
            return nullptr;
        }
        TreeNode* cur = new TreeNode(preorder[0]);
        //找到目前結點在中序周遊中的位置，此索引左邊為左子樹，右邊為右子樹
        vector<int>::iterator mid = find(inorder.begin(), inorder.end(), preorder[0]);
        int left_nodes = mid - inorder.begin();//目前結點的左子樹有left_nodes個

        vector<int> left_inorder(inorder.begin(), mid);
        vector<int> right_inorder(mid+1, inorder.end());
        vector<int> left_preorder(preorder.begin()+1, preorder.begin()+left_nodes+1);
        vector<int> right_preorder(preorder.begin()+left_nodes+1, preorder.end());
        cur->left = buildTree(left_preorder, left_inorder);
        cur->right = buildTree(right_preorder, right_inorder);
        return cur;
    }      

注意：我們很容易從整個樹的中序周遊結果得到左右子樹中序周遊的結果，然而根據整個樹的先序周遊結果得到左右子樹先序周遊的結果還需要一定的計算

我們從中序周遊結果得到根結點後，擷取根結點在目前序列的索引left_nodes，此索引則表明左子樹共有left_nodes個結點。

貼一個西電的機試題

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Node{
    char data;
    Node* left;
    Node* right;
    Node(char data){
        this->data = data;
        this->left = nullptr;
        this->right = nullptr;
    }
};

vector<char> getCharArray(string str){
    vector<char> res;
    for(char c : str){
        res.push_back(c);
    }
    return res;
}

Node* getTree(vector<char>& preOrder, vector<char>& inOrder){
    if(preOrder.empty()){
        return nullptr;
    }
    Node* root = new Node(preOrder[0]);//構造根結點
    vector<char>::iterator mid = find(inOrder.begin(), inOrder.end(), preOrder[0]);
    int left_nodes = mid - inOrder.begin();
    vector<char> left_inOrder(inOrder.begin(), mid);
    vector<char> right_inOrder(mid+1, inOrder.end());
    vector<char> left_preOrder(preOrder.begin()+1, preOrder.begin()+1+left_nodes);
    vector<char> right_preOrder(preOrder.begin()+1+left_nodes, preOrder.end());
    root->left = getTree(left_preOrder, left_inOrder);
    root->right = getTree(right_preOrder, right_inOrder);
    return root;
}

void postOrder(Node* root){
    if(root == nullptr){
        return ;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->data;
}

int main(){
    string pre_str;
    string in_str;
    while(cin >> pre_str >> in_str){
        vector<char> preOrder = getCharArray(pre_str);
        vector<char> inOrder = getCharArray(in_str);
        Node* root = getTree(preOrder, inOrder);
        postOrder(root);
        cout<<endl;
    }
    return 0;
}