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

题意：给定树的中序遍历和先序遍历的结果，重新构建树

思路：

1. 用hashmap记录中序遍历的节点和的值和它们在中序遍历中的位置
2. 递归遍历preorder，每次把preorder的第一个节点拿出来，设为当前跟节点
3. 找出当前跟节点在中序遍历中的位置，来判断有多少个先序中的节点是当前节点的左子树，以及右子树
4. 根据找到的值构建当前节点的左右子树
5. 返回当前节点

思想：树的先序遍历

复杂度：时间O（n)，空间O(n)

class Solution {
    HashMap<Integer, Integer> map = new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len1 = preorder.length;
        int len2 = inorder.length;
        for(int i=0;i<len2;i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, inorder, 0, len1-1, 0, len2 - 1);    
    }
    
    TreeNode build(int[] preorder, int[] inorder, int ps, int pe, int is, int ie) {
        if(ps>pe)
            return null;
        TreeNode cur = new TreeNode(preorder[ps]);
        int index = map.get(preorder[ps]);  
        cur.left = build(preorder, inorder, ps+1, pe - ie + index, is, index-1);
        cur.right = build(preorder, inorder, pe - ie + index + 1, pe, index+1, ie);
        return cur;
    }
}