105.从前序与中序遍历序列构造二叉树

力扣题目链接(opens new window)

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

class Solution {
public:
    TreeNode* dfs(vector<int>& preorder,int prebeg,int preend,vector<int>& inorder,int inbeg,int inend){
        if(prebeg == preend) return nullptr;
        int tmp = preorder[prebeg];
        TreeNode* root = new TreeNode(tmp);
        if(preend - prebeg == 1) return root;

        //切割点
        int index;
        for(index = inbeg;index < inend;index++){
            if(inorder[index] == tmp) break;
        }

        //切割
        int leftinbeg = inbeg;
        int leftinend = index;
        int rightinbeg = index+1;
        int rightinend = inend;

        int leftprebeg = prebeg+1;
        int leftpreend = leftprebeg +index - inbeg;
        int rightprebeg = leftpreend;
        int rightpreend = preend;
        root->left = dfs(preorder,leftprebeg,leftpreend,inorder,leftinbeg,leftinend);
        root->right = dfs(preorder,rightprebeg,rightpreend,inorder,rightinbeg,rightinend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0) return nullptr;
        return dfs(preorder,0,preorder.size(),inorder,0,inorder.size());
    }
};