[BOJ 5639] 이진 검색 트리

 

 

---

문제 링크

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

5639번: 이진 검색 트리

---

문제 풀이

- 정적 클래스를 정의하여 주어진 입력값을 이진 검색 트리(전위 순회) 방식으로 정의

- 이전에 풀었던 트리 순회와 동일하게 재귀 함수 사용하여 후위 순회 구할 수 있도록 함 

- 노드의 최대 개수는 10^4 이고, 각 노드 별로 최대 2번 재귀를 호출할 때 O(2 * 10^4) 시간 복잡도 소요 

 

참고

https://dev-ljw1126.tistory.com/248

[BOJ 1991] 트리 순회

 

---

제출 코드

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

public class Main {
	
    static StringBuilder sb = new StringBuilder();

    static Node ROOT;

    static class Node {
        int value;
        Node left;
        Node right;

        public Node(int _value) {
            this.value = _value;
        }

        public void insert(int _value) {
            if(this.value > _value) {
                if(this.left == null) this.left = new Node(_value);
                else this.left.insert(_value);
            } else {
                if(this.right == null) this.right = new Node(_value);
                else this.right.insert(_value);
            }
        }
    }

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true) {
            String input = br.readLine();

            if(input == null || "".equals(input)) break;

            int value = Integer.parseInt(input);

            if(ROOT == null) ROOT = new Node(value);
            else ROOT.insert(value);
        }

        br.close();
    }

    // 후위 순회 - 왼쪽 오른쪽 부모
    static void postorder(Node node) {
        if(node == null) return;

        postorder(node.left);
        postorder(node.right);
        sb.append(node.value).append("\n");
    }

    static void pro() {
        postorder(ROOT);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}