根据前序、中序遍历重构二叉树

 1 public class ReconstructBinaryTree {
 2     public static void main(String[] args) {
 3         new ReconstructBinaryTree().reConstructBinaryTree(new int[] { 1, 2, 4,
 4                 7, 3, 5, 6, 8 }, new int[] { 4, 7, 2, 1, 5, 3, 8, 6 });
 5     }
 6 
 7     public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
 8         return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0,
 9                 in.length - 1);
10     }
11 
12     public TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre,
13             int[] in, int startIn, int endIn) {
14 
15         if (startPre > endPre || startIn > endIn)
16             return null;
17 
18         TreeNode root = new TreeNode(pre[startPre]);// 构造树根
19         for (int i = startIn; i <= endIn; i++) {
20             // 中序遍历中找树根
21             if (in[i] == pre[startPre]) {
22 
23                 root.left = reConstructBinaryTree(pre, startPre + 1, i
24                         - startIn + startPre, in, startIn, i - 1);
25                 root.right = reConstructBinaryTree(pre, i - startIn + startPre
26                         + 1, endPre, in, i + 1, endIn);
27                 break;
28             }
29         }
30 
31         return root;
32     }
33 }
34 
35 class TreeNode {
36     int val;
37     TreeNode left;
38     TreeNode right;
39 
40     TreeNode(int x) {
41         val = x;
42     }
43 }