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

#풀이

import org.w3c.dom.Node;

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

public class Main {
    static class Node{
        int v;
        Node left,right;

        Node(int input){
            this.v = input;
        }
        void insert(int num){
            if(v<num){
                if(right==null)right = new Node(num);
                else right.insert(num);
            }
            if(v>num){
                if(left==null)left = new Node(num);
                else left.insert(num);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Node root = new Node(Integer.parseInt(br.readLine()));
        while(true){
            String input = br.readLine();
            if(input==null||input.equals(""))break;
            root.insert(Integer.parseInt(input));
        }
        postOrder(root);


    }

    static void postOrder(Node node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.v);
    }
}

#성능

#정리

전위 순회의 경우 처음에 탐색한 값이 항상 트리의 루트가 되므로, 입력의 첫 번째 값을 루트 노드로 설정했다.
그 이후 반복문을 돌면서 입력된 값을 insert 함수를 통해 이진 탐색 트리에 삽입했다.
삽입 시 현재 노드의 값보다 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 내려가며, 해당 위치가 비어 있으면 새 노드를 생성하고, 그렇지 않으면 재귀적으로 다시 삽입을 시도하도록 구현했다.
트리가 모두 구성된 후에는 후위 순회 함수를 정의하여, 왼쪽 자식 → 오른쪽 자식 → 현재 노드 순으로 재귀적으로 방문하며 노드의 값을 출력하도록 했다.