105. Construct Binary Tree from Preorder and Inorder Traversal

前序和后序不能确定唯一的二叉树因为：前序根左右，中序左根右，后序左右根。前序和后序代表的都是节点的上下关系，只有中序遍历代表了节点的左右关系。只有同时知道了左右和上下的关系才能确定唯一的二叉树。

这题是前序和中序确定一个二叉树，递归主体框架还是

dfs() {
    if (...) return null;
    root = TreeNode(val)
    root.left = dfs(preorder(range), inorder(range))
    root.right = dfs(preorder(range), inorder(range))
return root
}

需要找出这几个值。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return helper(preorder, inorder, 0, 0, inorder.length - 1);
}

public TreeNode helper(int[] preorder, int[] inorder, int pl, int il, int ir) {
    if (pl > preorder.length - 1 || il > ir) { // il = ir 时创建单个节点
        return null;
    }
    TreeNode root = new TreeNode(preorder[pl]);
    int inRootPos = 0;
    for (int i = il; i <= ir; i++) {
        if (inorder[i] == root.val) {
            inRootPos = i;
        }
    }
    root.left = helper(preorder, inorder, pl + 1, il, inRootPos - 1);
    root.right = helper(preorder, inorder, pl + inRootPos - il + 1, inRootPos + 1, ir); // pl加上左子树的宽度(inRootPos - il + 1)
    return root;
}