[백준] 트리순회

📖 문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

✍ 입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

📄 출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

✅ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static Map<String, String[]> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());        // 트리 노드의 갯수

        while(N-- > 0) {
            String[] split = br.readLine().split(" ");
            String parent = split[0];
            String left = split[1];
            String right = split[2];

            map.put(parent, new String[]{left, right});
        }

        preOrder("A");
        System.out.println();
        inOrder("A");
        System.out.println();
        postOrder("A");
    }

    // 전위 순회
    public static void preOrder(String val) {
        if(".".equals(val)) return;
        System.out.print(val);
        preOrder(map.get(val)[0]);
        preOrder(map.get(val)[1]);
    }

    // 중위 순회
    public static void inOrder(String val) {
        if(".".equals(val)) return;
        inOrder(map.get(val)[0]);
        System.out.print(val);
        inOrder(map.get(val)[1]);
    }

    // 후위 순회
    public static void postOrder(String val) {
        if(".".equals(val)) return;
        postOrder(map.get(val)[0]);
        postOrder(map.get(val)[1]);
        System.out.print(val);
    }
}

🧩 코드풀이

재귀를 통해 전위 순회, 중위 순회, 후위 순회 메서드를 구현해두고 깊이우선탐색을 구현하여 문제를 아래와 같은 순서로 해결했습니다.
1. 입력으로 들어오는 3개의 문자열을 각자 부모 노드, 왼쪽 노드, 오른쪽 노드로 분리하여 Map에 담았습니다. Map의 값에는 String 문자열로 0번째 인덱스에는 왼쪽 노드, 1번째 인덱스에는 오른쪽 노드가 오도록 했습니다.
2. 이후 재구위치와 출력 위치가 각각 다른 순회 메소들을 호출해서 순회 내용을 출력해줍니다.