根据前序遍历和中序遍历重建二叉树

这个题目是比较有名的一道题，选择题也经常遇到，可以利用递归的方式来解决。

参考原的bog地址为https://blog.csdn.net/weixin_41747893/article/details/104808459

    /*
    struct TreeNode
    {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x),left(NULL),right(NULL){}
    TreeNode(int x,TreeNode* p1,TreeNode* p2) : val(x),left(p1),right(p2){}
    };
    */

    //vector<int> preOrder = {3,9,6,7,20,15};
    //vector<int> minOrder = {6,9,7,3,15,20};
    //OK 写对了 pre是先序遍历 mid是中序遍历
    TreeNode* rebuild(vector<int>& pre, vector<int>& mid)
    {
        if(pre.size() == 0 || mid.size() == 0) return NULL;
        TreeNode* root = new TreeNode(pre[0]);
        int k = 0;//表示mid中根节点root的位置
        for(int i=0;i<mid.size();i++)
        {
            if(mid[i] == pre[0])
            {
                k = i;
                break;
            }
        }

        //重建左子树
        vector<int> leftPre;
        leftPre.assign(pre.begin()+1,pre.begin()+1+k);
        vector<int> leftMid;
        leftMid.assign(mid.begin(),mid.begin()+k);
        root->left = rebuild(leftPre,leftMid);

        //重建右子树
        vector<int> rightPre;
        rightPre.assign(pre.begin()+k+1,pre.end());
        vector<int> rightMid;
        rightMid.assign(mid.begin()+k+1,mid.end());
        root->right = rebuild(rightPre,rightMid);

        return root;

    }

感觉像是原来的博客用指针来做的话不用新建很多内存。

测试结果如下：

看了一个这个地址的写的也不错，直接用interator 来做不用新建这么多

https://www.cnblogs.com/cling-cling/p/12896848.html

0604 17：04新增最直观只这样算的，但是有一个疑惑：

root->right = helper(preorder,inorder,preStart+1+midIndex - inStart, midIndex+1,inEnd); //???为什么要加上 -inStart?????

    TreeNode* buildTreeByPreAndMid(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0)
        return NULL;
        TreeNode* newTreeNode = helper(preorder,inorder,0,0,preorder.size()-1);
        return newTreeNode;
        
    }

    //preStart表示以preorder[preStart]作为根节点 inStart表示以preorder[preStart]作为根节点的子树的所有节点在inorder中的起点位置
    //inEnd表示以preorder[preStart]作为根节点的子树在inorder中的结束位置
    TreeNode* helper(vector<int>& preorder,vector<int>& inorder,int preStart,int inStart,int inEnd)
    {
        if(preorder.size() == 0 || inStart > inEnd ) return NULL;
        TreeNode* root = new TreeNode(preorder[preStart]);

        int midIndex = 0;//在inorder中找到root的值  preorder和inorder各个值并不相同
        for(int i=inStart;i<=inEnd;i++)
        {
            if(inorder[i] == preorder[preStart])
            {
                midIndex = i;
                break;
            }
        }
        root->left = helper(preorder,inorder,preStart+1,inStart,midIndex-1);
    
        root->right = helper(preorder,inorder,preStart+1+midIndex  - inStart, midIndex+1,inEnd); //???为什么要加上 -inStart?????

        return root;

    }