version at: 2022-04-04

/**
1. 根据前序(根->左->右)和中序(左->根->右)数组重构整个树, 前中后指的是根的相对位置
2. 根据结构来看, 从中序序列的第一个值是根, 该值将前序序列分为两部分, 即可知道左右子树的前序序列
3. 知道左右子树的前序序列后, 我们就能通过子树的元素个数在中序序列中划分出左右子树的中序序列了
4. 如此递归下去, 就能重建整个树
5. 因为每个值是独一无二的, 所以可以用map优化下.
*/

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = inorder.length;
        return buildTree(preorder, 0, n-1, 
                         inorder, 0, n-1, 
                         IntStream.range(0, n).boxed().collect(Collectors.toMap(i->inorder[i], i->i)));
    }

    public TreeNode buildTree(int[] preorder, int pl, int pr, int[] inorder, int il, int ir, Map<Integer, Integer> map) {
        if (pl > pr || il > ir) return null;

        int index = map.get(preorder[pl]);
        int numL = index - il;

        return new TreeNode(preorder[pl],
                            buildTree(preorder, pl+1     , pl+numL, inorder, il     , index-1, map),
                            buildTree(preorder, pl+numL+1, pr     , inorder, index+1,ir      , map));
    }
}

/*
1. preorder: 根-左-右， inorder： 左-根-右
2. perorder从左到右遍历的点，对应在inorder中可将其划分成左子树段和右子树段
3. inorder划分后的子树节点数量必定对应与perorder对应，所有根据数量可反向划分perorder
4. 即可递归求解
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    Map<Integer, Integer> mapping = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0 ; i < inorder.length; i++)   mapping.put(inorder[i], i);
        return buildTree(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder, int pl, int pr, int il, int ir){
        if (pl > pr || il > ir) return null;
        TreeNode root = new TreeNode(preorder[pl]);
        int index = mapping.get(preorder[pl]);
        int leftNumber = index - il;

        root.left = buildTree(preorder, inorder, pl+1, pl+leftNumber, il, index -1);
        root.right = buildTree(preorder, inorder, pl+leftNumber+1, pr, index+1, ir);
        return root;
    }
}