题解 | #重建二叉树#

本题目要求根据二叉树的前序遍历与中序遍历重建二叉树，前序遍历顺序为“根-左-右”，中序遍历顺序为“左-根-右”，我们可以根据中序遍历中根节点的值确定前序遍历中的左子树区间与右子树区间，从而重建二叉树。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    unordered_map<int,int> hp;
    TreeNode* help(vector<int>& pre,int left,int right,int lo,int hi) {
        if(left == right) return nullptr;
        int rootval=pre[left];
        int index=hp[rootval];
        int leftlen=index-lo;
        TreeNode* root=new TreeNode(rootval);
        root->left=help(pre,left+1,left+1+leftlen,lo,index);
        root->right=help(pre,left+1+leftlen,right,index+1,hi);
        return root;
    }
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n=vin.size();
        for(int i=0;i<n;++i) {
            hp[vin[i]]=i;
        }
        return help(pre,0,n,0,n);
    }
};