【牛客题霸题解】重建二叉树（待更新 Java、py）

前序遍历：根左右
中序遍历：左根右
只看前序遍历的话，我们知道第一个节点是根。但是不知道左子树有多少个节点、右子树有多少个节点
知道了根节点是哪个以后，我们就可以根据中序遍历知道左右子树分别有多少个节点。

c++

class Solution {
public:
    void BuildTree(TreeNode* &root,vector<int>& pre,int preS,vector<int>& vin,int vinS,int len)
    {
        if(len == 0){return;}
        //记录一下根节点
        int n = pre[preS];
        root = new TreeNode(pre[preS]);
        int lnum = 0;
        for(int i = 0 ; i < len ; i++)
        {
            if(vin[vinS+i]==n)
            {
                break;
            }

            lnum++;

        }
        BuildTree(root->left,pre,preS+1,vin,vinS,lnum);
        BuildTree(root->right,pre,preS+1+lnum,vin,vinS+1+lnum,len-lnum-1);
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin){
        TreeNode* Root = NULL;
        int N = pre.size();
        BuildTree(Root,pre,0,vin,0,N);
        return Root;

    }
};