(Java) 백준 5639 : 이진 검색 트리

풀이1 : Tree, Node 클래스 생성하여 postorder메소드 재귀적으로 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Tree {
	Node root;
	
	Tree() {
		this.root = null;
	}
	
	public void insert(int key) {
		root = insertNode(root, key);
	}
	
	private Node insertNode(Node node, int key) {
		Node newNode = new Node(key, null, null);
		if(node==null) {
			return newNode;
		} else {
			if(node.key<key) {
				node.right = insertNode(node.right, key);
			} else if(node.key>key){
				node.left = insertNode(node.left, key);
			}
		}//if end
		
		return node;
	}//insertNode() end
	
	public void postOrder() {
		postOrderTraversal(root);
	}
	
	private void postOrderTraversal(Node node) {
		if(node==null) {
			return;
		}
		postOrderTraversal(node.left);
		postOrderTraversal(node.right);
		System.out.println(node.key);
	}
}

class Node {
	int key;
	Node left;
	Node right;
	
	Node(int key, Node left, Node right) {
		this.key = key;
		this.left = left;
		this.right = right;
	}
}

public class Main5639 {	
	public static void main(String[] args) throws IOException {
		Tree tree = new Tree();
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String numStr;
		while(true) {
			numStr = bf.readLine();
			if(numStr==null || numStr.equals("")) break;
			tree.insert(Integer.parseInt(numStr));
		}//while end
		tree.postOrder();
	}
}

 

풀이 2 : 배열로 구현 

출처 : https://girawhale.tistory.com/59

[백준] 5639번: 이진 검색 트리 - JAVA

BST의 특징을 이용한다.

전위 순회한 순서대로 값을 배열에 저장하면, 맨 앞이 부모노드이고, 그 뒤로 부모노드보다 값이 작은 좌측 자식 그룹이 나오다가 부모노드보다 값이 큰 값이 나오는 부분부터 우측 자식 그룹이다. 

이를 이용하여 후위 순회할 수 있게끔 코드를 재귀적으로 짤 수 있다.

 

import java.util.Scanner;

public class Main5639 {

	static int[] tree = new int[10001];
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int idx = 0;
		while(scanner.hasNext()) {
        	//전위 순회한 순으로 배열에 값을 저장한다.
			tree[idx++] = scanner.nextInt();
		}//while end
		postOrder(0,idx-1);
	}//main() end
	
	static void postOrder(int n, int end) {
		if(n>end) return;
        
		//n은 부모, n+1부터는 좌측 자식 그룹 시작
		int mid = n+1;
        
        	//mid변수를 우측자식노드가 시작하는 index까지 증가시킨다.
		while(mid<=end && tree[mid]<tree[n]) {
        	//부모노드(tree[n])보다 tree[mid]가 커지는 순간
        	//mid부터 우측 자식 그룹 시작
			mid++;
		}//while end
        
		/*
        	*while문 나온 mid는 우측 자식 그룹 첫번째 index
        	*인덱스 n+1부터 mid-1까지는 좌측 자식 그룹
        	*인덱스 mid부터 end까지는 우측 자식 그룹
        	*인덱스n은 부모노드
        	*/
		postOrder(n+1, mid-1);
		postOrder(mid, end);       
		System.out.println(tree[n]);
	}//postOrder() end
}