package AlgorithmTest;
/**
* Created by dell on 2015/10/5.
*/
public class RecreateBinaryTreeTest {
public static void main(String[] args) {
int[] preTraverseArr = new int[]{1, 2, 4, 7, 3, 5, 6, 8};
int[] midTreverseArr = new int[]{4, 7, 2, 1, 5, 3, 8, 6};
BinaryTree tree = BinaryTree.RecreateBinaryTree(preTraverseArr, midTreverseArr);
System.out.println("preOrder:");
tree.preOrderPrint();
System.out.println("midOrder:");
tree.midOrderPrint();
}
}
class BinaryTree {
private static class Node {
private int value;
private Node left;
private Node right;
public Node(int value){
this.value = value;
left = null;
right = null;
}
}
private Node root;
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public void preOrderPrint() {
preOrderPrint(root);
}
public void midOrderPrint() {
midOrderPrint(root);
}
private void preOrderPrint(Node root) {
if (root != null) {
System.out.println(root.value);
preOrderPrint(root.left);
preOrderPrint(root.right);
}
}
private void midOrderPrint(Node root) {
if (root != null) {
midOrderPrint(root.left);
System.out.println(root.value);
midOrderPrint(root.right);
}
}
public static BinaryTree RecreateBinaryTree(int[] preTraverseArr, int[] midTreverseArr) {
Node root = RecreateBinaryTree(preTraverseArr, 0, midTreverseArr, 0, preTraverseArr.length);
BinaryTree tree = new BinaryTree();
tree.setRoot(root);
return tree;
}
private static Node RecreateBinaryTree(int[] preTraverseArr, int be1,int[] midTreverseArr, int be2, int length) {
if (0 != length){
Node root = new Node(preTraverseArr[be1]);
int index = findNum(midTreverseArr, be2, length, preTraverseArr[be1]);
int leftLength = index - be2;
int rightLenght = be2 + length - 1 - index;
Node nodeleft = RecreateBinaryTree(preTraverseArr, be1 + 1, midTreverseArr, be2, leftLength);
Node noderight = RecreateBinaryTree(preTraverseArr, be1 + leftLength + 1, midTreverseArr, index + 1, rightLenght);
root.left = nodeleft;
root.right= noderight;
return root;
}
return null;
}
private static int findNum(int[] array, int be, int length, final int findNum){
for (int i = be; i < be + length; ++i){
if (findNum == array[i]){
return i;
}
}
return -1;
}
}