[백준 1991] 트리 순회 - JAVA

BOJ Link

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

 

풀이 과정

BST의 순회법 3가지를 구현하는 문제다.

 

left, right가 자식노드의 레퍼런스를 가리키는 일반적인 방법에서 조금 바꿔서 인덱스 기반으로 풀었다.

 

입력이 노드의 순서대로 주어지지 않기 때문에 이점만 유의하면 된다.

 

제출 코드

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

class Main {
    static Node[] tree;
    static StringBuilder sb = new StringBuilder();

    static class Node {
        int value;
        public int left;
        public int right;

        public Node(int value, int left, int right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        tree = new Node[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int val = st.nextToken().charAt(0) - 'A';
            int left = st.nextToken().charAt(0);
            int right = st.nextToken().charAt(0);

            Node node = new Node(val, -1, -1);
            if (!isDot(left)) node.left = left - 'A';
            if (!isDot(right)) node.right = right - 'A';

            tree[val] = node;
        }

        preorder(0);
        sb.append("\n");
        inorder(0);
        sb.append("\n");
        postorder(0);
        System.out.println(sb);
    }

    public static boolean isDot(int num) {
        return num == '.';
    }

    public static void append(int num) {
        sb.append((char) ('A' + num));
    }

    public static void preorder(int num) {
        if (num == -1) return;
        append(num);
        preorder(tree[num].left);
        preorder(tree[num].right);
    }

    public static void inorder(int num) {
        if (num == -1) return;
        inorder(tree[num].left);
        append(num);
        inorder(tree[num].right);
    }

    public static void postorder(int num) {
        if (num == -1) return;
        postorder(tree[num].left);
        postorder(tree[num].right);
        append(num);
    }
}