1. 문제 설명 📌

2. 구현 방법 🗃️

KEY WORD: 재귀, DFS

해당 문제에서 실행해야 하는 작업에는 3가지로 왼쪽 자식 방문, 현 노드에 대한 처리, 오른쪽 자식 방문가 있다. 해당 문제는 '이 순서를 어떻게 할 것인가?'에 대한 기준을 세우면 쉽게 풀린다. 왜냐하면, 전위, 중위, 후위 순회는 미리 정해진 순서를 재귀적으로 반복하기 때문이다. 각 순회 별 3가지 작업에 대한 순서는 다음과 같다.

1️⃣ 전위 순회: 현 노드에 대한 처리➜ 왼쪽 자식 방문 ➜ 오른쪽 자식 방문
2️⃣ 중위 순회: 왼쪽 자식 방문 ➜ 현 노드에 대한 처리 ➜ 오른쪽 자식 방문
3️⃣ 후위 순회: 왼쪽 자식 방문 ➜ 오른쪽 자식 방문 ➜ 현 노드에 대한 처리

예를 들어 보면, 후위 순회를 진행한다고 해보자. 먼저 A를 방문할 것이고,

현재 노드에 대한 처리는 하지 않고 바로 B를 방문할 것이다.

B도 마찬가지로 현재 자신에 대한 처리는 하지 않고 D를 방문한다.

D는 자식이 없으므로, 앞의 두 과정을 생략하고, 바로 자신(현 노드)에 대한 처리를 한다. 해당 문제에서는 출력이 바로 현 노드에 대한 처리가 될 것이다.

현재 D
다음 다시 B로 돌아가보자. B 또한 오른쪽 자식이 없기에 자신에 대한 처리로 이어진다.

현재 DB
A로 돌아왔으나, A는 오른쪽 자식이 있다. 따라서 C로 간다.

C는 왼쪽 자식이 있다. 따라서 E로 간다. 근데, E도 자식이 없으니, 바로 자신에 대한 처리로 이어진다.

현재 DBE
지금까지 출력된 문자는 DBE이다. C는 오른쪽 자식이 있기에 F를 방문할 것이고, F는 왼쪽 자식 없이 오른쪽 자식만 있기에 G를 방문할 것이다.

G는 자식이 없기에 자신에 대한 출력으로 이어진다.

현재 DBEG

이제 출력되지 않고, 남은 F,C,A를 보면, 왼쪽 자식과 오른쪽 자식에 대한 처리를 마쳤음으로, 자신에 대한 처리를 행할 차례다. 따라서 재귀를 마치고 돌아오는 F ➜ C ➜ A 순으로 출력된다.

최종 DBEGFCA

(1) 시간복잡도 분석 🕓

노드의 개수 N이 많아야 26개이다. 이진 트리임으로, 간선의 개수도 많아야 25개이다. 따로 시간복잡도를 신경써야 하는 문제는 아니다.

3. 코드 소개 🔎

(1) SUDO CODE

0️⃣ 자신의 자식 번호를 멤버 변수로 가지는 Node 클래스 만들기, 해당 클래스를 26개짜리 배열로 만들기
1️⃣ 입력을 int형으로 변환해서 받고 트리 완성 시키기
2️⃣ 위에 설명한 순서대로 재귀하는 전위, 중위, 후위 함수 만들기
3️⃣ 각 순회의 값 모아 출력하기 위해 StringBuilder를 3개 만들고, 각각의 값을 저장
4️⃣ 한 번에 3가지 차례대로 출력

(2) JAVA CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Main {

    private static class Node {
        int left;
        int right;

        public Node () {

        }
    }
    // 'A' = 65, '.' = 46
    static int N;
    static StringBuilder[] ans = new StringBuilder[3];
    static Node [] nodes = new Node[26];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = st.nextToken().charAt(0) - 65;
            int left  = st.nextToken().charAt(0) - 65;
            int right = st.nextToken().charAt(0) - 65;

            if(nodes[start] == null) nodes[start] = new Node();
            nodes[start].left = left;
            nodes[start].right = right;
        }
        ans[0] = new StringBuilder();
        ans[1] = new StringBuilder();
        ans[2] = new StringBuilder();
        preorder(0); inorder(0); postorder(0);
        System.out.println(ans[0]);
        System.out.println(ans[1]);
        System.out.println(ans[2]);
    }

    public static void preorder(int now) {
        if(now < 0) return;
        ans[0].append((char)(now + 65));
        preorder(nodes[now].left);
        preorder(nodes[now].right);
    }

    public static void inorder(int now) {
        if(now < 0) return;
        inorder(nodes[now].left);
        ans[1].append((char)(now + 65));
        inorder(nodes[now].right);
    }

    public static void postorder(int now) {
        if(now < 0) return;
        postorder(nodes[now].left);
        postorder(nodes[now].right);
        ans[2].append((char)(now + 65));
    }

}