이진 검색 트리

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

풀이

입력 값이 트리의 전위 순회한 결과이기 때문에 가장 먼저 들어오는 값이 루트 노드다.

먼저 배열에 입력값을 다 저장하고 이후 배열에서 노드를 하나씩 꺼내 트리를 구성해준다.

끝으로 후위 순회 함수를 구현해 루트에서 출발하여 탐색하고 value를 출력해주면 된다.

코드

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;


    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        ArrayList<Node> tree = new ArrayList<>();

        while (true) {
            String input = br.readLine();
            if (input == null || input.equals(""))
                break;
            tree.add(new Node(Integer.parseInt(input)));
        }
        Node root = tree.get(0);
        for(int i = 1;i<tree.size();i++) {
            Node child = tree.get(i);
            insertNode(root, child);
        }

        postOrder(root);

        bw.close();
        br.close();
    }
    private static void insertNode(Node root, Node child) {
        if(child.value < root.value) {
            if(root.left == null)
                root.left = child;
            else
                insertNode(root.left, child);
        }
        else {
            if(root.right == null)
                root.right = child;
            else
                insertNode(root.right, child);
        }
    }

    private static void postOrder(Node root) {
        if(root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.value);
    }
}

class Node {
    public int value;
    public Node left;
    public Node right;
    public Node parent;

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

}