思路

先序遍历：根左右 中序遍历：左根右 后序遍历：左右根

1. 根据前序和中序构建树并返回根节点。
2. 前序的数组preOrder特点是元素遵循 |根元素|左子树|右子树|；中序的数组inOrder特点为元素遵循 |左子树|根元素|右子树|，因此可以递归以下步骤来构建
   • 子树范围 left > right 时返回 null
   • 通过preOrder从0～preOrder.length遍历可以找到每个子树的根节点
   • 找到根元素后，构建根节点，然后根据根元素位置 (这里可以通过map提升查找速度) 分割左右子树范围并递归查找其左右子树根节点

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

    int[] preorder;
    int[] inorder;
    int head_index = 0;

    Map<Integer,Integer> inMap = new HashMap();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;
        this.preorder = preorder;
        this.inorder = inorder;
	// 构建位置索引map
        for(int i = 0; i< inorder.length; i++) {
            inMap.put(inorder[i],i);
        }
        return build(0 , inorder.length - 1);
    }

    // 前序遍历确认头节点，中序遍历确认左右子树
    TreeNode build(int left, int right) {
        // 无子节点
        if (left > right) return null;
        // 子树头节点
        int head = preorder[head_index];
        head_index ++;
        TreeNode headNode = new TreeNode(head);
        int index = left;
        index = inMap.get(head);
        // 构建左子树
        TreeNode leftNode = build(left, index - 1);
        // 构建右子树
        TreeNode rightNode = build(index + 1, right);
        headNode.left = leftNode;
        headNode.right = rightNode;
        return headNode;
    }
}

Q.E.D.