java 면접문제 - 이미 알고 있는 선순과 중순 두루
1650 단어 Java 면접 문제집
class Node {
public int data;
public Node left;
public Node right;
public Node() {
}
public Node(int data) {
this.data = data;
this.left=null;
this.left=null;
}
}
public class BinaryTree {
private Node root;
public BinaryTree() {
root=null;
}
//
public void postOrder(Node localRoot){
if(localRoot!=null){
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data+" ");
}
}
public void postOrder(){
this.postOrder(this.root);
}
public void initTree(int[] preOrder,int []inOrder){
this.root=this.initTree(preOrder, 0,preOrder.length-1,inOrder,0,inOrder.length);
}
public Node initTree(int[] preOrder, int start1, int end1, int[] inOrder, int start2,
int end2) {
if(start1>end1 || start2>end2){
return null;
}
int rootData=preOrder[start1];
Node head=new Node(rootData);
//
int rootIndex=findIndexInArray(inOrder,rootData,start2,end2);
int offSet=rootIndex-start2-1;//
//
head.left=initTree(preOrder,start1+1,start1+1+offSet,inOrder,start2,start2+offSet);
//
head.right=initTree(preOrder,start1+2+offSet,end1,inOrder,rootIndex+1,end2);
return head;
}
public int findIndexInArray(int[] inOrder, int rootData, int begin,
int end) {
for (int i = begin; i <= end; i++) {
if(inOrder[i]==rootData){
return i;
}
}
return -1;
}
public static void main(String[] args) {
BinaryTree bt=new BinaryTree();
int[]preOrder={1,2,4,8,9,5,10,3,6,7};
int[]inOrder={8,4,9,2,10,5,1,6,3,7};
bt.initTree(preOrder, inOrder);
System.out.println(" :");
bt.postOrder();
}
}