문제 바로가기

나의 풀이

트리를 구현하기 위해 Node 클래스와 nodeList를 내부적으로 가진 Tree 클래스를 만들어야했다.

대문자 A, B, C 등으로 주어지지만 우선 정수형으로 변환하여 트리를 만들었고 출력해줄 때 다시 문자형으로 파싱하여 출력해주기로 했다.

전위, 중위, 후위 순회는 학교 자료구조 시간에도 배웠던 알고리즘이지만 잠시 잊어버렸던 것 같다. 잘 기억해두도록 하자.

나의 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

class Main {

    static class Node {

        int data;
        Node leftChild;
        Node rightChild;
    }

    static class Tree {

        List<Node> nodeList = new ArrayList<>();

        public void createNode(int data, Node leftChild, Node rightChild) {
            Node node = new Node();
            node.data = data;
            node.leftChild = leftChild;
            node.rightChild = rightChild;
            nodeList.add(data, node);
        }

        public Node getNode(int data) {
            return nodeList.get(data);
        }

        public Node getRoot() {
            return nodeList.get(0);
        }

        public List<Integer> preOrder(List<Integer> list, Node node) {
            if (node == null) {
                return list;
            }
            list.add(node.data);
            list = preOrder(list, node.leftChild);
            list = preOrder(list, node.rightChild);
            return list;
        }

        public List<Integer> inOrder(List<Integer> list, Node node) {
            if (node == null) {
                return list;
            }
            list = inOrder(list, node.leftChild);
            list.add(node.data);
            list = inOrder(list, node.rightChild);
            return list;
        }

        public List<Integer> postOrder(List<Integer> list, Node node) {
            if (node == null) {
                return list;
            }
            list = postOrder(list, node.leftChild);
            list = postOrder(list, node.rightChild);
            list.add(node.data);
            return list;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Tree tree = new Tree();
        for (int i = 0; i < n; i++) {
            tree.createNode(i, null, null);
        }

        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            Node node = tree.getNode(s[0].charAt(0) - 'A');
            if (s[1].charAt(0) == '.') {
                node.leftChild = null;
            } else {
                node.leftChild = tree.getNode(s[1].charAt(0) - 'A');
            }
            if (s[2].charAt(0) == '.') {
                node.rightChild = null;
            } else {
                node.rightChild = tree.getNode(s[2].charAt(0) - 'A');
            }
        }

        List<Integer> preOrderList = tree.preOrder(new ArrayList<>(), tree.getRoot());
        List<Integer> inOrderList = tree.inOrder(new ArrayList<>(), tree.getRoot());
        List<Integer> postOrderList = tree.postOrder(new ArrayList<>(), tree.getRoot());

        System.out.println(parseIntListToString(preOrderList));
        System.out.println(parseIntListToString(inOrderList));
        System.out.println(parseIntListToString(postOrderList));
    }

    private static String parseIntListToString(List<Integer> list) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            char c = (char) (list.get(i) + 'A');
            sb.append(c);
        }
        return sb.toString();
    }
}