[Baekjoon] 22856: 트리 순회

문제

유사 중위 순회를 구현하는 문제이다.

 

풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q22856 {

    private static int n;
    private static int[][] tree;
    private static int visitCount;
    private static int lastNode;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        tree = new int[(n + 1) * 4][2];
        visitCount = 0;
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int parent = Integer.parseInt(input[0]);
            int left = Integer.parseInt(input[1]);
            int right = Integer.parseInt(input[2]);
            tree[parent][0] = left;
            tree[parent][1] = right;
        }

        inOrder(1);
        search(1);
        System.out.println(visitCount);
    }

    public static void inOrder(int cur) {
        if (tree[cur][0] != -1) {
            inOrder(tree[cur][0]);
        }
        lastNode = cur;
        if (tree[cur][1] != -1) {
            inOrder(tree[cur][1]);
        }
    }

    public static void search(int cur) {
        if (tree[cur][0] != -1) {
            visitCount++;
            search(tree[cur][0]);
            if (tree[cur][0] == lastNode) {
                System.out.println(visitCount);
                System.exit(0);
            }
            visitCount++;
        }
        if (tree[cur][1] != -1) {
            visitCount++;
            search(tree[cur][1]);
            if (tree[cur][1] == lastNode) {
                System.out.println(visitCount);
                System.exit(0);
            }
            visitCount++;
        }
    }
}

여기서 중요한 포인트는 노드의 끝 점을 어떻게 찾느냐이다. 끝 점에 도달하면 회귀하지 않고 바로 끝나야하기 때문이다.

노드의 끝 점은 트리 중위 순회를 통해 찾을 수 있다.

 

위 코드에서는 inOrder 메서드를 통해 값을 계속 저장시킨다. 값을 계속 덮어씌워 저장시키면 마지막 값만 남게된다.

 

회고

내 코드에선 System.exit(0)로 종료를 시켜버렸지만 그렇게 좋은 코드로 보긴 어렵다.

조건을 더 추가하여 return 시켜 마지막에 출력하는 방식으로 수정해봐야겠다.