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

1. 感觉要用到递归之类的方法，因为可以通过前序遍历的数组确定根节点，那么中序找到这个根节点后，其左边的为左子树，右边的为右子树，可以通过递归构建。
2. 写了个很丑陋的递归…就这样吧

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //两个哈希表存储<值，位置>
    HashMap PreMap = new HashMap<>();
    HashMap inMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i
            PreMap.put(preorder[i],i);
            inMap.put(inorder[i],i);
        }
        //感觉要用递归构建子树
        //根节点一定为preorder[0]
        TreeNode node = new TreeNode(preorder[0]);
        //preorder[0]在inorder里的位置
        int local = inMap.get(preorder[0]);

        if(local>=1) node.left = DFS(preorder,inorder,0,local-1);
        if(local+1<=preorder.length-1) node.right = DFS(preorder,inorder,local+1,preorder.length-1);

        return node;
    }
    public TreeNode DFS(int[] preorder,int[] inorder,int start,int end){
        //给出中序遍历的start和end 将其接起来
        if(start==end){
            TreeNode node = new TreeNode(inorder[start]);
            return node;
        }
        //否则找到inorder[start,end]在preorder出现位置最靠前的作为根节点
        int minlocal = PreMap.get(inorder[start]);
        int minvalue = inorder[start];
        for(int i=start;i<=end;i++){
            int nowlocal = PreMap.get(inorder[i]);
            int nowvalue = inorder[i];
            if(nowlocal
                minlocal=nowlocal;
                minvalue=nowvalue;
            }
        }
        //此时找到根节点为minvalue 进行DFS
        TreeNode node = new TreeNode(minvalue);
        if(start<=inMap.get(minvalue)-1) node.left = DFS(preorder,inorder,start,inMap.get(minvalue)-1);
        if(inMap.get(minvalue)+1<=end) node.right = DFS(preorder,inorder,inMap.get(minvalue)+1, end);
        return node;
    }