백준 1991 트리 순회(JAVA)

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

1991번: 트리 순회

 

 

풀이)

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

public class Main_BJ_1991_트리순회 {
    static int[][] tree;
    static int n;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        tree = new int[n+1][2];

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int root = st.nextToken().charAt(0) - 'A' + 1;
            int left = st.nextToken().charAt(0) - 'A' + 1;
            int right = st.nextToken().charAt(0) - 'A' + 1;


            tree[root][0] = left;
            tree[root][1] = right;
        }

        boolean[] visited = new boolean[n+1];
        preorder(1, visited);
        System.out.println();
        visited = new boolean[n+1];
        inorder(1, visited);
        System.out.println();
        visited = new boolean[n+1];
        postorder(1, visited);
    }//main
    private static void preorder(int node, boolean[] visited){
        visited[node] = true;
        System.out.print((char) (node-1+'A'));

        if(tree[node][0]>0 && !visited[tree[node][0]])
            preorder(tree[node][0], visited);

        if(tree[node][1]>0 &&!visited[tree[node][1]])
            preorder(tree[node][1], visited);
    }//preorder
    private static void inorder(int node, boolean[] visited){
        visited[node] = true;

        if(tree[node][0]>0 && !visited[tree[node][0]])
            inorder(tree[node][0], visited);

        System.out.print((char) (node-1+'A'));

        if(tree[node][1]>0 &&!visited[tree[node][1]])
            inorder(tree[node][1], visited);
    }//inorder
    private static void postorder(int node, boolean[] visited){
        visited[node] = true;

        if(tree[node][0]>0 && !visited[tree[node][0]])
            postorder(tree[node][0], visited);

        if(tree[node][1]>0 &&!visited[tree[node][1]])
            postorder(tree[node][1], visited);

        System.out.print((char) (node-1+'A'));
    }//postorder
}

문제에서 친절히 preorder, inorder, postorder의 순서를 알려줘서 재귀는 어렵지 않게 짤 수 있었다.

(출력을 처음, 중간, 마지막 중 하나로 선택하면 되니까!!)

 

다만, A, B, C와 index에 관련해서 어떻게 처리할지 고민이 있었다.

빨리 정해서 했으면 됐을텐데 밍기적거림..ㅎ

 

 

 

https://velog.io/@gandi0330/Java-%EB%B0%B1%EC%A4%80-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-1991%EB%B2%88

[Java] 백준 / 트리 순회 / 1991번

이 블로그처럼 class를 따로 만들어 노드를 생성하는 것이 참 깔끔하고 좋은것 같다.