[PS] 백준 5639번 이진 검색 트리

https://www.acmicpc.net/problem/5639

문제 설명

임의의 이진 검색 트리(BST)가 있을 때, 이 BST에 대한 전위 순회 결과주어진다. 이 BST에 대한 후위 순회를 구하는 문제이다.

복습겸 BST를 설명하면 아래와 같다.

1. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
2. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
3. 왼쪽 오른쪽 서브트리도 BST이다.

문제 풀이

전위 순회는 현재 노드의 키 - 왼쪽 서브트리 전위 순회 - 오른쪽 서브트리 전위 순회 이므로 BST의 모든 서브트리의 루트 노드부터 방문한다. 따라서, 삽입 순서에 따라서 형태가 달라지는 BST 이지만 전위 순회 결과 순서대로 BST에 삽입하면 동일한 BST를 얻을 수 있다.

그리고 그 BST에 대해서 후위 순회한 결과를 출력하면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.StringTokenizer;

class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static Scanner sc = new Scanner(System.in);
	static StringTokenizer st;
	
	static class Bst {
		Node root;
		
		void insert(int data) {
			if (root == null) {
				root = new Node(data);
				return;
			}
			
			Node curNode = root;
			while (true) {
				if (data >= curNode.data) {
					if (curNode.right == null) {
						curNode.right = new Node(data);
						return;
					}
					
					curNode = curNode.right;
				} else {
					if (curNode.left == null) {
						curNode.left = new Node(data);
						return;
					}
					
					curNode = curNode.left;
				}
			}
		}
		
		void postOrder(Node cur) throws Exception {
			if (cur == null) {
				return;
			}
			
			postOrder(cur.left);
			postOrder(cur.right);
			bw.append(cur.data + "\n");
		}
	}
	
	static class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {
			super();
			this.data = data;
		}

	}
	
	static Bst bst;

	public static void main(String[] args) throws Exception {
		bst = new Bst();
		String line;
		while ((line = br.readLine()) != null) {
			int num = Integer.parseInt(line);
			
			bst.insert(num);
		}
		
		bst.postOrder(bst.root);
		bw.flush();
	}
}