剑指offer(四)：重建二叉树

题目：

　　输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解决办法：

　　前序遍历的第一个元素是根节点，然后进行中序遍历找出该根节点，此时该根节点左侧的为左子树，右侧为右子树，再构建左子树的左子树同理，故可使用递归

代码：

 1 import java.util.*;
 2 public class Solution {
 3     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
 4         if(pre== null || in == null){
 5             return null;
 6         }
 7         
 8         Map<Integer,Integer> map = new HashMap<Integer,Integer>();
 9         for(int i=0;i<in.length;i++){
10             map.put(in[i],i);
11         }
12         return construct(pre,0,pre.length-1,in,0,in.length-1,map);
13     }
14     public static TreeNode construct(int pre[],int ps,int pe,int mid[],int ms,int me,Map<Integer,Integer> map){
15         if(ps > pe){
16             return null;
17         }
18         //先得到根节点在中序遍历中的位置，她前面的是左节点，后面的是右节点
19         int rootIndex = map.get(pre[ps]);
20         TreeNode head = new TreeNode(pre[ps]);
21         //左
22         head.left = construct(pre,ps+1,ps+rootIndex-ms,mid,ms,rootIndex-1,map);
23         //右
24         head.right = construct(pre,ps+rootIndex-ms+1,pe,mid,rootIndex+1,me,map);
25         return head;
26     }
27 }
28 
29 class TreeNode {
30     int val;
31     TreeNode left;
32     TreeNode right;
33     TreeNode(int x) { val = x; }
34 }

补充：前序遍历和中序遍历，中序遍历和后序遍历均可以确定一棵唯一的二叉树，但是前序遍历和后序遍历就不能确定一棵唯一的二叉树如下:

图片来源：https://blog.csdn.net/u010429424/article/details/72841219