一、题目

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

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

二、思路

* 1 每次从preorder中拿到当前数组首部的数（这里我们用一个栈来实现），作为当前树根。

* 2 然后在inorder中找到该数的索引（用hashmap来实现），其左边作为左子树，右边作为右子树（注意这个顺序，前序一定是根左右）

* 3 注意一些特殊情况，我们用left和right来判断：

????????当left==right，说明走到同一节点了，无左右孩子，为叶子节点直接返回该节点 *

????????当left > right 说明没有左孩子或右孩子，模拟一遍就明白了

三、代码

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length == 1) return new TreeNode(inorder[0]);
        Stack<Integer> preStack = new Stack<>();
        HashMap<Integer, Integer> inorderHash = new HashMap<>();
        for (int i = 0,j = inorder.length -1; i < inorder.length; i++,j--) {
            preStack.push(preorder[j]);
            inorderHash.put(inorder[i], i);
        }
        TreeNode root = bdTree(0,inorder.length-1,inorderHash,preStack);
        return root;
    }

    public TreeNode bdTree(int left, int right,HashMap<Integer,Integer> inHash, Stack<Integer> preStack) {
        if (left == right) return new TreeNode(preStack.pop());  // 当前是叶子节点
        if (left > right) return null; // 当前节点无左孩子或右孩子
        int rootVal = preStack.pop();
        int rootIndex = inHash.get(rootVal);
        TreeNode root = new TreeNode(rootVal);  // 根
        root.left = bdTree(left,rootIndex-1,inHash,preStack); // 左
        root.right = bdTree(rootIndex+1,right,inHash,preStack); // 右
        return root;
    }
}