[백준] 트리 순회 JAVA 풀이 (트리, 재귀, DFS)

🔗 문제 링크

문제 링크: https://www.acmicpc.net/problem/1991

---

📌 문제 개요

백준 1991번 트리 순회는 이진 트리의 노드 정보가 주어졌을 때,

전위 순회 / 중위 순회 / 후위 순회 결과를 출력하는 문제

 

각 입력은 부모 왼쪽자식 오른쪽자식 형태로 주어지며,
'.' 은 자식이 없다는 뜻

 

루트 노드는 항상 A 이므로, A부터 시작해서 세 가지 순회

---

📌 접근 방법

처음에는 트리를 객체로 직접 연결해야 하나 고민할 수 있지만,
이 문제는 노드 개수가 많지 않고 각 노드가 왼쪽 자식 / 오른쪽 자식만 가지는 이진 트리이기 때문에
배열 두 개만으로도 충분히 해결할 수 있습니다.

 

저는 다음과 같이 접근했습니다.

• left[] : 각 노드의 왼쪽 자식 저장
• right[] : 각 노드의 오른쪽 자식 저장

예를 들어 입력이 A B C 라면

• A의 왼쪽 자식은 B
• A의 오른쪽 자식은 C

이므로 left[A-'A'] = 'B', right[A-'A'] = 'C' 로 저장하면 됩니다.

이후 루트 노드 A부터 재귀 순회를 돌리면 됩니다.

---

📌 핵심 아이디어

이 문제의 핵심은 트리 구조 저장과 순회 순서 구분

 

1. 트리 구조 저장

각 노드마다 왼쪽 자식과 오른쪽 자식만 알면 되므로
배열 두 개로 충분합니다.

• left[idx]
• right[idx]

여기서 idx = parent - 'A' 로 문자를 배열 인덱스로 변환

---

2. 순회 차이는 출력 시점만 다르다

전위 순회

• 현재 노드 출력
• 왼쪽 서브트리 순회
• 오른쪽 서브트리 순회

중위 순회

• 왼쪽 서브트리 순회
• 현재 노드 출력
• 오른쪽 서브트리 순회

후위 순회

• 왼쪽 서브트리 순회
• 오른쪽 서브트리 순회
• 현재 노드 출력

즉, 재귀 구조는 거의 같고 출력 위치만 다릅니다.

---

3. 종료 조건 처리

 

입력에서 '.' 은 자식이 없다는 뜻입니다.
따라서 재귀 함수에서 현재 노드가 '.' 이면 바로 종료

---

📌 전체 코드

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

public class Main {

    static char[] left = new char[26];
    static char[] right = new char[26];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char parent = st.nextToken().charAt(0);
            char l = st.nextToken().charAt(0);
            char r = st.nextToken().charAt(0);

            int idx = parent - 'A';
            left[idx] = l;
            right[idx] = r;
        }

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

    static void preOrder(char node) {
        if (node == '.') return;

        System.out.print(node);
        preOrder(left[node - 'A']);
        preOrder(right[node - 'A']);
    }

    static void inOrder(char node) {
        if (node == '.') return;

        inOrder(left[node - 'A']);
        System.out.print(node);
        inOrder(right[node - 'A']);
    }

    static void postOrder(char node) {
        if (node == '.') return;

        postOrder(left[node - 'A']);
        postOrder(right[node - 'A']);
        System.out.print(node);
    }
}

---

📄 정리

처음에는 트리 연결 구조를 복잡하게 생각할 수 있지만,

이 문제는 각 노드의 왼쪽/오른쪽 자식만 저장하면 되기 때문에
배열 두 개로 간단하게 처리할 수 있습니다.

 

또한 전위 / 중위 / 후위 순회의 차이는
재귀 안에서 출력하는 위치만 다르다는 점을 이해하면 쉽게 구현

트리 순회 기초를 익히기에 좋은 문제