[BOJ 1991] 트리 순회

 

 

 

---

문제 링크

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

1991번: 트리 순회

---

문제 풀이

전위 순회(preodrer) : 부모 > 왼쪽 > 오른쪽
중위 순회(inorder) : 왼쪽 > 부모 > 오른쪽
후위 순회(postorder) : 왼쪽 > 오른쪽 > 부모

 

- 알파벳 26개 그리고 알파벳 노드별 자식 2개(왼쪽, 오른쪽) 

- 전위/중위/후위 순회로 인해 총 3번 로직 수행 

- 한 노드당 최대 2번 재귀 호출을 수행하므로 O(26 * 2 * 3) 시간 복잡도 소요

 

처음 해당 문제를 접했을 때 그래프 탐색으로 풀어보려 했지만 풀지 못하였다.

역시나 기술 블로그를 찾아보았고, 2차원 배열을 선언 -> (char) 알파벳 아스키 코드값 활용하여 인덱스 구하고 왼쪽, 오른쪽 자식 노드 정의 -> 재귀 함수로 출력 구하는 방법을 익힐 수 있었다

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
	
    static StringBuilder sb = new StringBuilder();

    static int N;

    static int[][] tree;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        tree = new int[27][2];

        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = st.nextToken().charAt(0) - 'A';

            for(int j = 0; j < 2; j++) {
                char child = st.nextToken().charAt(0);

                if(child != '.') tree[parent][j] = (child - 'A');
                else tree[parent][j] = -1;
            }
        }

    }

    // 전위 순회 - 루트, 왼쪽, 오른쪽
    static void preorder(int node) {
        if(node == -1) return;

        sb.append((char)(node + 'A'));
        preorder(tree[node][0]);
        preorder(tree[node][1]);
    }

    // 중위 순회 - 왼쪽, 루트, 오른쪽
    static void inorder(int node) {
        if(node == -1) return;

        inorder(tree[node][0]);
        sb.append((char)(node + 'A'));
        inorder(tree[node][1]);
    }

    // 후위 순회 - 왼쪽, 오른족, 루트
    static void postorder(int node) {
        if(node == -1) return;

        postorder(tree[node][0]);
        postorder(tree[node][1]);
        sb.append((char)(node + 'A'));
    }

    static void pro() {
        int rootNode = 0;

        preorder(rootNode);
        sb.append("\n");

        inorder(rootNode);
        sb.append("\n");

        postorder(rootNode);
        sb.append("\n");

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}