题意

给出一颗二叉树的前序遍历与中序遍历，重建一颗唯一对应的二叉树，之后返回其头节点。

思路

依据前序遍历与中序遍历的定义，前序遍历的第一个节点就为整棵树的根节点，我们在中序遍历中找到这个节点，那么左边的部分就是左子树的部分，右边的部分就是右子树的部分，再递归对左右子树分别重复这个查询的过程，最终就可以重建出整棵树。

/**
 * 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* ans = new TreeNode(pre[0]);//根节点为前序遍历第一个节点
        int i;
        for(i=0;i<vin.size();i++) if(vin[i]==pre[0]) break;//在中序遍历中寻找根节点
        vector<int> preL,preR,vinL,vinR=vector<int>();
        for(int j=1;j<=i;j++) preL.push_back(pre[j]);
        for(int j=0;j<=i;j++) vinL.push_back(vin[j]);
        for(int j=i+1;j<pre.size();j++){preR.push_back(pre[j]);vinR.push_back(vin[j]);}//构造下一次搜索左右子树的前序遍历与中序遍历
        ans->left = reConstructBinaryTree(preL,vinL);
        ans->right = reConstructBinaryTree(preR,vinR);//搜索左右子树
        return ans;
    }
};

复杂度分析

时间复杂度：$O(nlogn)O(nlogn)$，循环查找$nn$次，平均每次消耗时间$O(logn)O(logn)$。

空间复杂度：$O(n)O(n)$，存储答案所用空间开销。