[SWEA] #1231 중위순회

Link

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD&categoryId=AV140YnqAIECFAYD&categoryType=CODE

---

Code

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

class Solution {
    static ArrayList<ArrayList<Integer>> tree;
    static HashMap<Integer, String> alpha;
    public static void inorder(int x) {
        ArrayList<Integer> arr = tree.get(x);
        if (arr.size() > 0) {
            inorder(arr.get(0));
        }
        System.out.print(alpha.get(x));
        if (arr.size() > 1) {
            inorder(arr.get(1));
        }
    }
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int testCase = 1; testCase <= 10; testCase++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), "");
            int N = Integer.parseInt(st.nextToken());
            tree = new ArrayList<>();
            tree.add(new ArrayList<>());
            alpha = new HashMap<>();
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                tree.add(new ArrayList<>());
                int x = Integer.parseInt(st.nextToken());
                String a = st.nextToken();
                alpha.put(x, a);
                while(st.hasMoreTokens()) {
                    int y = Integer.parseInt(st.nextToken());
                    tree.get(x).add(y);
                }
            }
            System.out.printf("#%d ", testCase);
            inorder(1);
            System.out.println();
        }
    }
}

---

Solution

인접리스트를 이용해 트리를 구성하고 HashMap을 이용하여 각 인덱스에 맞는 글자를 미리 지정해둔다.
그후 중위순회를 돌면서 현재 글자를 출력하면 해결
전위순회 : Root - Left - Right
중위순회 : Left - Root - Right
후위순회 : Left - Right - Root