문제 이해

이진 검색 트리는 세 가지 조건을 만족하는 이진 트리이다.

1. 왼쪽 자식 값 < Node 값

2. 오른쪽 자식 값 > Node 값

3. 왼쪽 자식, 오른쪽 자식을 Root로 하는 서브트리도 이진 검색 트리

전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하라.

---

문제 풀이

전위 검색 트리는 루트 ⇒ 왼쪽 자식 Node ⇒ 오른쪽 자식 Node 순으로 출력하는 검색법이다.
즉 처음 입력된 값이 Root Node이며, 입력되는 값이 Root Node보다 작은 경우는 모두 왼쪽 Subtree, 커질 경우 오른쪽 Subtree로 Node값이 이동할 것이다(이진 검색 트리 특징)

또한 전위 검색의 특징상, 항상 현재 Tree 중 Leaf Node에 입력받은 값이 들어가게 된다.이유는 아래와 같다.
전위 검색은 루트가 먼저 출력되고, 왼쪽과 오른쪽 자식 Node 순으로 출력받는다. 즉, 왼쪽과 오른쪽 자식 Node가 입력 받기 전에 루트가 먼저 출력된다는 소리이며, 루트가 출력될 당시에는 왼쪽, 오른쪽 자식 Node가 Tree에 추가된 상태가 아니므로 루트는 출력될 당시에는 Leaf Node일 것이다.

따라서, Root Node를 처음에 입력된 Node로 설정 이후 Tree를 재구성한 뒤, 이진 검색 트리를 후위 순회하였다.

---

코드

import java.io.*;
import java.util.*;

class Node{
	int value;
	Node left;
	Node right;
	Node parent;
	
	public Node(int value){
		this.value = value;
		left = null;
		right = null;
		parent = null;
	}
}


public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static ArrayList<Integer> nodes = new ArrayList<>();
	static Node root = null;
	
	static void postorder(Node n) {
		if(n.left!=null) postorder(n.left);
		if(n.right!=null) postorder(n.right);
		sb.append(n.value+"\n");
	}
	
	static void makeNode(Node node, int value) {
		if(node.value < value) {
            // 이진 검색 트리의 특성 상 오른쪽 SubTree에 추가되어야 할 Node
			if(node.right==null) { 
            // 오른쪽이 비었으므로 오른쪽 자식으로 추가(Leaf Node) 
				node.right = new Node(value);
				return;
			}
			makeNode(node.right, value); // 오른쪽 SubTree로 들어감
		}
		else {
            // 이진 검색 트리 특성 상 왼쪽 SubTree에 추가되어야 할 Node
			if(node.left==null) { 
            // 왼쪽이 비었으므로 왼쪽 자식으로 추가(Leaf Node)
				node.left = new Node(value);
				return;
			}
			makeNode(node.left, value); // 왼쪽 SubTree로 들어감
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		BufferedReader br 
                = new BufferedReader(new InputStreamReader(System.in));
		String input="";
		
		while((input = br.readLine())!=null) {
			if(input.equals("")) break; 
             // readLine()으로 입력받을 경우 
             // ""을 마지막에 입력 받는 경우가 있어 추가해주었다.
			if(root==null) {
				root = new Node(Integer.parseInt(input));
				continue;
                // 처음 입력되었을 경우. Root Node를 설정해준다.
			}
			makeNode(root, Integer.parseInt(input));
            // Root Node를 통해 Tree를 만든다
		}
		
		postorder(root);
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과