package tree;
public class Node{
private Node left;
private Node right;
private int data;
public Node(int data){
this.data=data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
package tree;
/*
50
/\
40 60
/\ /\
30 45 55 70
/\
20 35
*/
public class ConstructBSTFromInorderAndPostOrderTraversal {
public static void main(String[] args) {
new ConstructBSTFromInorderAndPostOrderTraversal();
}
public ConstructBSTFromInorderAndPostOrderTraversal() {
int inorder[] = {20, 30, 35, 40, 45, 50, 55, 60, 70};
int postorder[] = {20, 35, 30, 45, 40, 55, 70, 60, 50};
int inStart = 0;
int inEnd = inorder.length-1;
int postStart =0;
int postEnd = postorder.length-1;
Node n = buildTree(inorder, inStart, inEnd, postorder, postStart, postEnd);
System.out.println(n);
}
public Node buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd){
if(inStart > inEnd || postStart > postEnd)
return null;
int rootValue = postorder[postEnd];
Node root = new Node(rootValue);
int k=0;
for(int i = inStart; i <= inEnd; i++){
if(inorder[i]==rootValue){
k = i;
break;
}
}
int len = k - inStart;
root.setLeft(buildTree(inorder, inStart, k-1, postorder, postStart, postStart+len-1));
root.setRight(buildTree(inorder, k+1, inEnd, postorder, postStart+len, postEnd-1));
return root;
}
}
No comments:
Post a Comment