思路:

• 先序遍历顺序是(中左右) 中序遍历顺序是(左右中)
• 从先序遍历中找到根节点，中序遍历中根节点的左边就是左子树，右边就是右子树
• dfs递归处理每一个根节点
• 那么我们就需要以下几个信息:根节点(从先序遍历中找),左子树(从中序遍历中找),右子树(从中序遍历中找)
• dfs(inorder,preorder,pl,pr,il,ir)
• pl代表当前先序遍历的起点(根节点) pr代表当先先序遍历的终点(在中序遍历中找长度)
• il同理

时间复杂度(O(n))

• 分析只先序遍历中的节点最多只会被遍历一遍
• 所以时间复杂度的分歧出现在在中序遍历中找到根节点
• 如果每个都进来遍历一遍，那么最坏就是O(N^2)
• 所以开一个哈希表把中序遍历里的值和下标先存下来，这个找根节点的过程就变成了O(1)
• 总的时间复杂度为O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<Integer,Integer> pos = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        for(int i = 0 ; i < n ; i++)
            pos.put(inorder[i],i);
        return dfs(preorder,inorder,0,n-1,0,n-1);
    }

    private TreeNode dfs(int[] preorder,int[] inorder,int pl,int pr,int il,int ir){
        if(pl > pr)
            return null;
        int rootVal = preorder[pl];
        int rootIn = pos.get(rootVal);
        int lenLeft = rootIn - il;
        TreeNode root = new TreeNode(rootVal);
        root.left = dfs(preorder,inorder,pl+1,pl+lenLeft,il,lenLeft-1);
        root.right = dfs(preorder,inorder,pl+lenLeft+1,pr,rootIn+1,ir);
        return root;
    }
}