Q. 1991 자바 : 트리 순회

Q. 1991 자바 : 트리 순회

 

문제 : boj.kr/1991

실버 1 난이도의 문제이다.

 

이진 트리가 주어졌을 때 전위, 중위, 후위 순회를 해 결과를 출력하는 문제이다.

주의해야 할 점은 이진 트리로 입력이 주어지며, 자식이 없을 경우 '.'으로 주어진다는 점 이다.

 

아래와 같은 방식으로 풀이했다.

1. 저장을 List에 해야하므로, 입력값을 int로 변환하는 과정이 필요했고, 

입력은 유효한 값이 주어지므로(A-Z 사이의 값) root 노드의 값 - 'A'를 계산해 int로 변환한 뒤 자식들을 이 인덱스를 가진 List 안에 저장했다.

2. 순회를 할 때는 list에 들어있는 값 - 'A'를 이용해 자식 노드에 방문했고, 출력을 할 때는 현재 인덱스 + 'A'를 문자열로 반환해 출력했다.

 

이진 트리의 노드의 수 N이 최대  26이므로 시간 복잡도는 상수 시간 안에 모든 순회가 가능하다.

문제를 풀 때 자료형 변환에 신경을 써서 해결했다. 

---

풀이는 아래와 같다.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

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

    static int n;
    static ArrayList<Character>[] child;

    static void input() {

        n = scan.nextInt();
        child = new ArrayList[n];

        for (int i = 0; i < n; i++) child[i] = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int root = scan.next().charAt(0) - 'A';
            char child1 = scan.next().charAt(0);
            child[root].add(child1);
            char child2 = scan.next().charAt(0);
            child[root].add(child2);
        }

    }

    static void preOrder(int x) {

        sb.append((char) (x + 'A'));

        for (char y: child[x]) {
            if (y == '.') continue;
            preOrder(y - 'A');
        }
    }

    static void inOrder(int x) {
        if (child[x].isEmpty()) {
            sb.append((char)(x + 'A'));
        }else {
            if (child[x].get(0) != '.') inOrder(child[x].get(0) - 'A');
            sb.append((char) (x + 'A'));
            if (child[x].get(1) != '.') inOrder(child[x].get(1) - 'A');
        }
    }

    static void postOrder(int x) {

        for (int y: child[x]) {
            if (y == '.') continue;
            postOrder(y - 'A');
        }
        sb.append((char) (x + 'A'));
    }

    static void pro() {
        preOrder(0);
        sb.append('\n');
        inOrder(0);
        sb.append('\n');
        postOrder(0);
        System.out.println(sb);
    }

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


    static class FastReader {
        // BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}