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

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

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

1. 一开始的想法是通过判断先序遍历节点的后驱在中序遍历中的索引下标是不是在该节点之前,以此来确定一个节点的左孩子,但是要想直接找到右孩子情况非常复杂。(还要区分当前节点是左孩子还是右孩子,其左孩子的右孩子是不是为空...)。
2. 关于树的算法从原子操作的角度思考非常重要，树的定义本来就是一种递归，子树也是一个树，左子树和右子树拼接起来就是一颗新树。中序序列中一个节点的左边全是左子树，右边全是右子树，通过左子树的区间长度就可以找到前序序列中的左子树区间。基于这种思想可以用迭代方法解决这个问题：

 public TreeNode buildTree(int[] preorder, int[] inorder) { 
     for(int i=0;i<preorder.length;i++)
     hashmap.put(inorder[i],i);
     return build(preorder,inorder,0,inorder.length-1,0,inorder.length-1);
    }
 public TreeNode build(int[] preorder, int[] inorder,int pl,int pr,int il,int ir)
  {
    if(il>=inorder.length||pl>pr||il>ir)
    return null;
    int index=hashmap.get(preorder[pl]);
    int len=index-il,len2=ir-index;
    TreeNode root=new TreeNode(preorder[pl]);
    if(pl==pr)
    return root;
    root.left=build(preorder,inorder,pl+1,pl+len,il,index-1);
    root.right=build(preorder,inorder,pl+len+1,pl+len+len2,index+1,ir);
    return root;
  }