아이디어

• ‘왼쪽 자식 < 부모 < 오른쪽 자식’임을 이용해 입력이 들어오면 루트부터 계속 비교하여 트리를 구성한다.
  • 부모보다 작을 경우 왼쪽으로 간다. 클 경우 오른쪽으로 간다. 같은 키를 가지는 경우는 주어지지 않는다.
  • 해당 자리가 비어있을 경우 자신이 자식이 된다.
  • 이미 누군가 있을 경우 다시 비교해서 왼쪽/오른쪽을 찾아간다.
• 전위 탐색하며 노드 키를 출력한다.
  • 전위 탐색: ‘루트→왼쪽 노드→오른쪽 노드’ 식으로 탐색하는 법
  • 재귀를 이용하면 된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        Node root = new Node(Integer.parseInt(rd.readLine()));

        String s;
        while ((s = rd.readLine()) != null) {
            root.addChild(Integer.parseInt(s));
        }
        root.printPostfix(wr);
        wr.flush();
    }
}

class Node {
    Node left, right;
    int val;

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

    void addChild(int n) {
        if (n < this.val) {
            if (left == null)
                left = new Node(n);
            else
                left.addChild(n);
        }
        else {
            if (right == null)
                right = new Node(n);
            else
                right.addChild(n);
        }
    }

    void printPostfix(BufferedWriter wr) throws Exception {
        if (left != null)
            left.printPostfix(wr);
        if (right != null)
            right.printPostfix(wr);
        wr.append(Integer.toString(val));
        wr.append("\n");
    }
}

메모리 및 시간

• 메모리: 18612 KB
• 시간: 516 ms

리뷰

• 트리 탐색에 대한 기초 개념을 묻는 문제
• 내가 보았던 문제 중에 이런 게 있었던 게 생각이 난다. ‘전위 탐색과 중위 탐색의 결과가 주어졌을 때, 후위 탐색의 결과를 출력하시오.’
  • 이번 문제는 대소 관계로 쉽게 비교할 수 있어서 됐지만 이런 경우는 어떻게 해야할까?