<剑指offer> 第4题

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重构出该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复的数字。

例如：

前序遍历序列{1，2，4，7，3，5，6，8}

中序遍历序列{4，7，2，1，5，3，8，6}

重建二叉树并输出它的头节点

思路：

1.由前序遍历的第一个节点可知根节点为1，由此可以把中序遍历分为两部分，左边部分为根节点的左子树{4，7，2}（inOrder），右边部分为根节点的右子树{5，3，8，6}（inOrder）

2.由{4，7，2}（inOrder）与前序遍历对比知其前序遍历为{2，4，7}（preOrder）

　可知2为左子树第一级的“根节点”，其左子树为{4，7}（inOrder）,其右子树为空，其前序遍历为{4，7}（preOrder）

　可知4为左子树第二级的“根节点”，其左子树为空，右子树为{7}

　到此，左子树遍历完成，右子树同理

3.将以上思路递归

代码实现

public class Third {
   class TreeNode{
       int val;
       TreeNode left;
       TreeNode right;
       public TreeNode(int val){
           this.val = val;
       }
   }

   public void reConstructBST(int[] pre, int[] in){
        reBuildBST(pre, 0, pre.length - 1, in, 0, in.length - 1);
   }

   private TreeNode reBuildBST(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd){
       if(preStart > preEnd || inStart > inEnd){
           return null;
       }
       TreeNode root = new TreeNode(pre[preStart]);
       for(int i = 0; i < inEnd; i ++){
           if(in[i] == pre[preStart]){
               root.left = reBuildBST(pre, preStart, preStart + i - inStart, in, inStart, i - 1);
               root.right = reBuildBST(pre, preStart + i - inStart + 1, preEnd, in, i + 1, inEnd);
           }
       }
       return root;
   }
}