java实现——006重建二叉树

 1 public class T006 {
 2     public static void main(String[] args){
 3         int pre[] = {1,2,4,7,3,5,6,8};
 4         int in[] = {4,7,2,1,5,3,8,6};
 5         preorderTraversalRec(construct(pre,in,8));
 6 
 7     }
 8     public static void preorderTraversalRec(TreeNode root) {
 9         if (root == null) {
10             return;
11         }
12         System.out.print(root.val + " ");
13         preorderTraversalRec(root.left);
14         preorderTraversalRec(root.right);
15     }
16     public static TreeNode construct(int[] pre,int[] in,int length){
17         if(pre == null ||in == null||length<=0)
18             return null;
19         return constructCore(pre,in,0,length-1,0,length-1);
20         
21     }
22     public static TreeNode constructCore(int[] pre,int[] in,int startPre,int endPre,int startIn,int endIn){
23         int rootValue = pre[startPre];
24         TreeNode root = new TreeNode(rootValue);
25         root.left = null;
26         root.right = null;
27         if(startPre == endPre){
28             if(startIn == endIn&&startPre==startIn){
29                 System.out.println("root");
30                 return root;
31             }
32         }    
33         int rootIn = startIn;
34         while(rootIn<=endIn&&in[rootIn]!=rootValue){
35             ++ rootIn;
36         }
37         if(rootIn == endIn&&in[rootIn]!=rootValue){
38             System.out.println("Invalid input2");
39         }
40         int leftLength = rootIn - startIn;
41         int leftPreEnd = startPre + leftLength;
42         if(leftLength>0){
43             root.left = constructCore(pre,in,startPre+1,leftPreEnd,startIn,rootIn-1);
44         }
45         if(leftLength<endPre-startPre){
46             root.right = constructCore(pre,in,leftPreEnd+1,endPre,rootIn+1,endIn);
47         }
48         return root;
49         
50     }
51     private static class TreeNode {
52         int val;
53         TreeNode left;
54         TreeNode right;
55 
56         public TreeNode(int val) {
57             this.val = val;
58         }
59     }
60 }