剑指 Offer：07. 重建二叉树

 3
/ \\

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

public TreeNode recursive(int preStart, int inStart, int inEnd, int[] preOrder, int[] inOrder){
    // 
    if(inStart > inEnd || preStart > preOrder.length - 1){
        return null;
    }

    // 创建根节点，根节点即为先序遍历中的第一个元素
    TreeNode root = new TreeNode(preOrder[preStart]);
    // 用于存储不同子树的根节点的索引位置
    int index = 0;

    // 在中序遍历中找到根节点 root 的位置，然后拆分出来左右子树
    for(int i = inStart; i <= inEnd; i++){
        if(root.val == inOrder[i]){
            // 此时 root 在中序遍历中的索引位置为 i
            index = i;
            break;
        }
    }

    // 递归拆分左右子树
    // index-instart+1 就是当前节点左子树的数量加上当前节点的数量
    // 所以preStart+(index-instart+1)就是当前节点右子树前序遍历开始的位置

    root.left = recursive(preStart + 1, inStart, index - 1, preOrder, inOrder);
    root.right = recursive(preStart + index - inStart + 1, index + 1, inEnd, preOrder,inOrder);

    return root;
}