題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

解題思路：
在二叉樹的前序遍歷序列中，第一個(gè)數(shù)字總是樹的根節(jié)點(diǎn)的值。
在中序遍歷序列中，根節(jié)點(diǎn)的值在序列的中間。根據(jù)前序遍歷找到根節(jié)點(diǎn)后，中序遍歷序列中，位于根節(jié)點(diǎn)左邊的是左子樹的結(jié)點(diǎn)的值，位于根節(jié)點(diǎn)右邊的是右子樹的結(jié)點(diǎn)的值。

如下圖所示，前序遍歷序列的第一個(gè)數(shù)字1就是根結(jié)點(diǎn)的值。掃描中序遍歷序列，就能確定根結(jié)點(diǎn)的值的位置。根據(jù)中序遍歷特點(diǎn)，在根結(jié)點(diǎn)的值1前面的3個(gè)數(shù)字都是左子樹結(jié)點(diǎn)的值，位于1后面的數(shù)字都是右子樹結(jié)點(diǎn)的值。

示例

同樣，在前序遍歷的序列中，根結(jié)點(diǎn)后面的3個(gè)數(shù)字就是3個(gè)左子樹結(jié)點(diǎn)的值，再后面的所有數(shù)字都是右子樹結(jié)點(diǎn)的值。這樣我們就在前序遍歷和中序遍歷兩個(gè)序列中，分別找到了左右子樹對應(yīng)的子序列。

既然我們已經(jīng)分別找到了左、右子樹的前序遍歷序列和中序遍歷序列，我們可以用同樣的方法分別去構(gòu)建左右子樹。也就是說，接下來的事情可以用遞歸的方法去完成。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if( pre.empty() )
            return NULL;
        TreeNode* root = new TreeNode( pre[0] );
        
        vector<int> left_pre, left_vin, right_pre, right_vin;
        
        //left_vin
        for( int i=0;vin[i]!=root->val;i++ )
            left_vin.push_back(vin[i]);
        //right_vin
        for( int i=left_vin.size()+1;i<vin.size();i++)
            right_vin.push_back(vin[i]);
        //left_pre
        for( int i=1;i<=left_vin.size();i++ )
            left_pre.push_back(pre[i]);
        //right_pre
        for( int i=left_vin.size()+1;i<pre.size();i++ )
            right_pre.push_back(pre[i]);
        
        root->left = reConstructBinaryTree( left_pre, left_vin );
        root->right = reConstructBinaryTree( right_pre, right_vin );
        
        return root;
    }
};