重建二叉树

题目一：根据前序遍历和后续遍历重建

思路：

因为前序遍历的第一个节点是根节点，所以先在中序序列中找到根节点，由于是中序序列，所以根节点左边是左子树，根节点右边是右子树，再在左右子树中依次进行上述过程，递归进行就可以重建这棵二叉树。
preStart:前序序列的开始index,以此来确定根节点。
inStart,inEnd:中序序列的起始index，遍历此范围的中序序列，找到根节点在中序序列中的位置。

Paste_Image.png

public TreeNode buildTree(int[] preorder,int[] inorder){
       helper(0,0,inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart,int inStart,int inEnd,int[] preorder,int [] inorder)
{
      if(preStart>inorder.length-1||inStart>inEnd)
             return null;
        TreeNode root=new TreeNode(preorder[preStart]);
        int inIndex;
        for(int i=inStart;i<=inEnd;i++){
               if(root.val==inorder[i])
                      inIndex=i;
         }
        root.left=helper(preStart+1,inStart,inIndex-1,preorder,inorder);
        root.right=helper(preStart+inIndex-inStart+1,inIndex+1,inEnd.preorder,inorder);
        return root;
}