[백준] 5639 : 이진 검색 트리 - 자바(JAVA)

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

5639번: 이진 검색 트리

 

문제 해석

이진트리는 다음의 조건을 만족한다.

노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 부모 노드의 키보다 작다.

노드의 오른쪽 서브트리에 있는 모든 노드의 키는 부모 노드의 키보다 크다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 후위 순회한 결과를 구하는 프로그램을 작성하라.

 

문제 풀이 전 설계

이진 검색 트리를 전위 순회한 결과를 통해 이진트리를 생성한다.

생성한 이진트리를 가지고 후위 순회한 결과를 출력한다.

 

문제 풀이 하면서 생각

처음에 배열을 만들어서 풀려고 하였으나 오히려 생각해야 할 조건들이 더 많았던 것 같아 Node 클래스를 만들어서 이진트리를 생성합니다.

 

또한 전위순회의 특성을 이용해서 이진 검색 트리를 만드려고 하니까 더 복잡해져서 그냥 입력값을 통해 새로운 이진 검색 트리를 만든다는 생각으로 접근해야 훨씬 간단했습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

class Node {
	int num;
	Node left, right;

	public Node(int num) {
		this.num = num;
	}

	void insert(int num) {
		if (num < this.num) {
			if (this.left == null) {
				this.left = new Node(num);
				return;
			}
			this.left.insert(num);
			return;
		}
		if (this.right == null) {
			this.right = new Node(num);
			return;
		}
		this.right.insert(num);

	}

}

public class Main_5639_이진검색트리 {

	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		List<Integer> preOrderedList = new ArrayList<Integer>();

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		Node root = new Node(Integer.parseInt(br.readLine()));
		String str;
		while (true) {
			str = br.readLine();
			if (str == null) {
				break;
			}
			if(str.isEmpty()) {
				break;
			}
			root.insert(Integer.parseInt(str));			
		}
		
		postOrder(root);
		System.out.println(sb);
		// printPostOrderedList(1);
	}
	
	private static void postOrder(Node node) {
		if(node.left != null) {
			postOrder(node.left);
		}
		if(node.right != null) {
			postOrder(node.right);
		}
		sb.append(node.num + "\n");
	}
	

}