105. 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解析

这个题要算好左右子树的长度，然后用递归去解决。

class Solution {
    HashMap<Integer,Integer> orderMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //前序遍历的第一个节点就是根节点，然后在中序遍历中找到该节点，左边就是左子树，右边是右子树
        for(int i = 0 ;i < inorder.length;i++){
            orderMap.put(inorder[i],i);
        }
        return helper(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
    public TreeNode helper(int[] preorder, int[] inorder,int preStart,int preEnd,int orderStart,int orderEnd){
        if(preStart>preEnd||orderStart>orderEnd) return null;
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        //代表root的位置
        int inorderIndex = orderMap.get(rootVal);
        int leftLen = inorderIndex-1 - orderStart +1;
        int rightLen = orderEnd - inorderIndex ;

        root.left = helper(preorder,inorder,preStart+1,preStart+leftLen,orderStart,inorderIndex-1);
        root.right = helper(preorder,inorder,preStart+1+leftLen,preEnd,inorderIndex+1,orderEnd);
        return root;
    }
}

注意：本文归作者所有，未经作者允许，不得转载