根据先序中序还原二叉树

先序遍历：根 —> 左 —> 右

中序遍历：左 —> 根 —> 右

后序遍历：左 —> 右 —>根

算法思想：

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;
}