题目是 105. 从前序与中序遍历序列构造二叉树

这一题和 106. 从中序与后序遍历序列构造二叉树非常像，具体的处理方法是类似的，不同的地方在于，这一题我们把先序遍历的数组左侧的元素当作根节点，在代码中体现为preLeft++，而且先构造左子树，然后构造右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int[] preorder;
    int[] inorder;
    int preLeft;
    Map<Integer, Integer> map;
    public TreeNode myBuildTree(int inLeft, int inRight){
        if(inRight<inLeft) return null;
        TreeNode root=new TreeNode(preorder[preLeft]);
        int rootVal =preorder[preLeft];    //根节点
        int inorderRootIndex=map.get(rootVal);   //在中序遍历中定位根节点的索引
        preLeft++;
        root.left=myBuildTree(inLeft, inorderRootIndex-1);
        root.right=myBuildTree(inorderRootIndex+1, inRight);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder=preorder;
        this.inorder=inorder;
        preLeft=0;
        int inlen=inorder.length;
        map=new HashMap<>();
        for(int i=0; i<inorder.length; i++){
            map.put(inorder[i], i);
        }

        return myBuildTree( 0, inlen-1);
    }
}