[백준 1991번] 트리 순회

문제 링크: 1991번 트리 순회

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

 

순회하는 것보다 Java에서 char과 int 사이 캐스팅이 더 헷갈렸다.

왜 따로따로 캐스팅하면 계산이 안 되는지에 대해서 나중에 다시 알아봐야겠다.

 

그리고 트리의 노드들이 순서대로 제시되지 않을 때에는 해당하는 행에 맞추어 넣어준다.

 

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void printPath(ArrayList<Integer> path) {
        for (int i = 0; i < path.size(); i++) {
            char cur = (char)(path.get(i) + 'A');
            System.out.print(cur);
        }
    }

    public static void preorder(int[][] tree, int row, ArrayList<Integer> path) {
        // 현재 노드 방문 처리
        path.add(tree[row][0]);
        // 왼쪽 노드로 이동
        if (tree[row][1] != -1) preorder(tree, tree[row][1], path);
        // 오른쪽 노드로 이동
        if (tree[row][2] != -1) preorder(tree, tree[row][2], path);
    }

    public static void inorder(int[][] tree, int row, ArrayList<Integer> path) {
        // 왼쪽 노드로 이동
        if (tree[row][1] != -1) inorder(tree, tree[row][1], path);
        // 현재 노드 방문 처리
        path.add(tree[row][0]);
        // 오른쪽 노드로 이동
        if (tree[row][2] != -1) inorder(tree, tree[row][2], path);
    }

    public static void postorder(int[][] tree, int row, ArrayList<Integer> path) {
        // 왼쪽 노드로 이동
        if (tree[row][1] != -1) postorder(tree, tree[row][1], path);
        // 오른쪽 노드로 이동
        if (tree[row][2] != -1) postorder(tree, tree[row][2], path);
        // 현재 노드 방문 처리
        path.add(tree[row][0]);
    }

    public static void main(String[] args) {
        /* 입력 */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] tree = new int[n][3];

        for (int i = 0; i < n; i++) {
            // 순서가 섞여서 들어올 수도 있으니까,
            // 해당하는 노드 자리에 넣어주도록 row를 구해준다.
            int row = (int)(sc.next().charAt(0) - 'A');
            tree[row][0] = row;

            int left, right;
            for (int j = 1; j <= 2; j++) {
                char cur = sc.next().charAt(0);
                if (cur == '.') tree[row][j] = -1;
                else tree[row][j] = (int)(cur - 'A');
            }
        }

        /* preorder, inorder, postorder 결과 구하기 */
        ArrayList<Integer> preorderPath = new ArrayList<Integer>();
        preorder(tree, 0, preorderPath);

        ArrayList<Integer> inorderPath = new ArrayList<Integer>();
        inorder(tree, 0, inorderPath);

        ArrayList<Integer> postorderPath = new ArrayList<Integer>();
        postorder(tree, 0, postorderPath);

        /* 출력 */
        printPath(preorderPath); System.out.println();
        printPath(inorderPath); System.out.println();
        printPath(postorderPath); System.out.println();
        
        sc.close();
    }
}