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

题目：biubiu
题意：给出二叉树的前序和中序遍历，构造这个二叉树。

二叉树的前序第一个是根节点，二叉树的中序，第一个是最左叶子，通过前序和中序能够确定具体二叉树。

方法1：
首先确定根节点，前序的第一个为根节点，它的下一个值判断在中序的位置，如果在中序中该值在根节点的左边，那他就是左子树，否则就是右子树。

class Solution {
public:
   
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        TreeNode* root=new TreeNode(preorder[0]);
        unordered_mapmp;
        for(const auto&p:preorder){  ///判断前序的节点在中序的具体位置，如果这个节点为根节点，其左边就是左子树，右边就是右子树
            for(int j=0;js;///存父节点
        s.push(root);
        for(int i=1;ival]>mp[preorder[i]]){ ///左儿子
                p->left=new TreeNode(preorder[i]);
                s.push(p->left);
            }else{    ///右儿子
                k=p;
                s.pop();
                while(s.size()){
                    p=s.top();
                   if(mp[p->val]>mp[preorder[i]])
                       break;
                    //t=p;
                    
                    k=p;
                    s.pop();
                }
                
                  k->right=new TreeNode(preorder[i]);
                 // s.push(k);
                  s.push(k->right);
                //}
               
            }
            
        }
        return root;
    }
};

方法二：
使用递归，确定左右子树在数组中的区间，递归求解。

class Solution {
public:
   
    
    TreeNode* dfs(vector& preorder, vector& inorder,int x,int y,int k,int z){
        if(x>y)///x,y表示preorder中的区间，k,z表示inorder的区间，通过前序和中序确定四个值
        return NULL;
        if(x>preorder.size()){
            return NULL;
        }
        TreeNode* root=new TreeNode(preorder[x]);
        root->left=dfs(preorder,inorder,x+1,x+mp[preorder[x]]-k,k,mp[preorder[x]]-1);
        root->right=dfs(preorder,inorder,x+mp[preorder[x]]-k+1,y,mp[preorder[x]]+1,z);
        return root;
    }
    TreeNode* buildTree(vector& preorder, vector& inorder) {
            for(int i=0;imp;
};