LeetCode105：从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

先序遍历的顺序是根节点，左子树，右子树。中序遍历的顺序是左子树，根节点，右子树。

进行一波思想洗礼：以上面的示例一为测试数据
preorder = [3,9,20,15,7] 根左右 所以根是第一个数即3
inorder = [9,3,15,20,7] 左根右
因为从preorder中判断3是跟了，从而将inorder分成左子树和右子树
即左子树：inorder [9]
右子树：inorder [15,20,7]
把相应的前序遍历的数组也加进来

左子树
preorder[9]
inorder [9]

右子树
preorder[20 15 7]
inorder [15,20,7]
现在我们只需要构造左子树和右子树即可，然后重复上边的步骤继续划分，直到 preorder 和 inorder 都为空，返回 null 即可；我们不需要真的把 preorder 和 inorder 切分了，只需要分别用两个指针指向开头和结束位置即可。注意下边的两个指针指向的数组范围是包括左边界，不包括右边界。

思路： 我们只需要根据先序遍历得到根节点，然后在中序遍历中找到根节点的位置，它的左边就是左子树的节点，右边就是右子树的节点。
生成左子树和右子树就可以递归的进行了。

解答区大佬的图解，方便理解

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

private TreeNode build(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd) {
    //递归终止条件，两个数组越界之一就是条件
    if (pStart > pEnd || iStart > iEnd){
        return null;
    }

    //先构造根节点，根节点的值由先序遍历数组的第一个值确定
    int rootVal = preorder[pStart];
    TreeNode root = new TreeNode(rootVal);

    //递归左子树,首先通过rootVal在inorder中的索引（index），然后就能够知道inorder中左子树和右子树的边界
    int index = -1;
    for (int i = iStart; i <= iEnd; i++) {
        if (rootVal == inorder[i]){
            index = i;
            break;
        }
    }

    //通过inorder中左子树节点的数目来确定preorder中左右子树的边界
    int leftNum = index - iStart
    //最终确认好preorder和inorder中的左右子树边界，边界值包左不包右
    root.left = build(preorder, pStart + 1, pStart + leftNum, inorder, iStart, index - 1);
    root.right = build(preorder, pStart + leftNum + 1, pEnd, inorder, index + 1, iEnd);
    return root;
}