1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| //solution.java
public class solution {
public static void main(String [] args){
int pre[] ={1,2,4,7,3,5,6,8};
int in[] = {4,7,2,1,5,3,8,6};
TreeNode tree = reConstructBinaryTree(pre, in);
postTraverse(tree);
}
public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
int lengthpre = pre.length;
int lengthin = pre.length;
if (lengthin != lengthpre)
return null;
TreeNode tree = new TreeNode(pre[0]);
tree.left = null;
tree.right = null;
if (lengthin == 1)
return tree;
int i;
for (i = 0; i < lengthin; i++) {
if (tree.val == in[i])
break;
}
if (i > 0) {
int leftin[] = new int[i];
int leftpre[] = new int[i];
for (int j = 0; j < i; j++) {
leftin[j] = in[j];
leftpre[j] = pre[j + 1];
}
tree.left = reConstructBinaryTree(leftpre, leftin);
}
if (i < lengthin - 1) {
int rightin[] = new int[lengthin - i - 1];
int rightpre[] = new int[lengthin - i - 1];
for (int j = 0; j < lengthin - i - 1; j++) {
rightin[j] = in[j + i + 1];
rightpre[j] = pre[j + 1 + i];
}
tree.right = reConstructBinaryTree(rightpre, rightin);
}
return tree;
}
public static void postTraverse(TreeNode tree) {
if (tree.left != null)
postTraverse(tree.left);
if (tree.right != null)
postTraverse(tree.right);
System.out.print(tree.val+" ");
}
}
|