leetcode<105. 从前序与中序遍历序列构造二叉树><106. 从中序与后序遍历序列构造二叉树>

TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int begin,int end,int& root)
    {
        if(begin>end) return nullptr;                       //区间内没有节点了就返回
        TreeNode* newnode = new TreeNode(preorder[root]);  //创建当前节点
        //在找中序中找位置
        int i;
        for(i = begin;i<=end;i++)
        {
            if(inorder[i] == preorder[root]) break;
        }
        root++; //标记位
        //将原数组分成三个部分 begin~i-1 ,i ,i+1~end
        newnode->left = _buildTree(preorder,inorder,begin,i-1,root); //连接左子树
        newnode->right = _buildTree(preorder,inorder,i+1,end,root);  //连接右子树
        return newnode;       //返回构建完的树
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;            //以引用的方式记录节点的下标，因为每次找的都是不同的节点
        return _buildTree(preorder, inorder,0,preorder.size()-1,i);
    }

TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int& root,int begin,int end)
    {
        if(begin>end) return nullptr;  //区间内没数则返回
        TreeNode* newnode = new TreeNode(postorder[root]);
        int i;
        for(i = begin;i<=end;i++)       //找当前节点在中序遍历中的位置
        {
            if(inorder[i]==postorder[root]) break;
        }
        //分割区间
        // begin~i-1, i , i+1~end
        root--;    //向前遍历
        newnode->right = _buildTree(inorder,postorder,root,i+1,end); //连接右节点
        newnode->left = _buildTree(inorder,postorder,root,begin,i-1); //连接左节点
        return newnode;    //返回构造好的节点
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = postorder.size()-1;  //从末尾开始遍历
        return _buildTree(inorder,postorder,i,0,postorder.size()-1);
    }