[백준 - 2263] 트리의 순회 - Java

문제 설명

2263번: 트리의 순회

 

접근 방법

해당 문제에서는 중위 순회 결과와 후위 순회 결과가 주어졌을 때 이를 통해 전위 순회 결과를 요구하고 있습니다. 이를 위해선 중위 순회 결과와 후위 순회의 결과로 트리를 재현하는 것이 우선입니다.

 

(참고로 '전위 순회 결과와 중위 순회의 결과' 그리고 '중위 순회 결과와 후위 순회 결과'로는 트리를 재현할 수 있지만, '전위 순회의 결과와 후위 순회의 결과'로는 트리를 재현할 수 없습니다.)

 

우선 이 문제에 접근하기 앞서 중위 순회와 후위 순회의 특성에 대해 알아야합니다.

 

중위 순회의 특성은 '(하위) 왼쪽 노드 - 상위 노드 - (하위) 오른쪽 노드' 순으로 탐색하므로, 루트 노드는 전체 중위 순회 결과 중 중간 지점에 위치하게 됩니다.

 

후위 순회의 특성은 '(하위) 왼쪽 노드 - (하위) 오른쪽 노드 - 상위 노드' 순으로 탐색하므로, 루트 노드는 전체 후위 순회 결과 중 마지막 지점에 위치하게 됩니다.

 

이때 중위 순회 결과 상 루트 노드 이전에 순회했던 노드들은 루트 기준 왼쪽 서브 트리에 해당되며, 루트 노드 이후에 순회되는 노드들은 루트 기준 오른쪽 서브 트리에 해당됩니다.

 

 

여기서 후위 순회 마지막으로 탐색된 노드와 중위 순회 중간 지점에서 탐색 된 노드는 루트 노드로 같습니다. 이 루트 노드의 지점을 중위 순회 결과로부터 얻어낸 뒤 이 지점을 기준으로 영역을 반으로 나누어 오른쪽 서브 트리와 왼쪽 서브 트리를 구성하도록 합니다.

 

이때 오른쪽 서브 트리를 우선적으로 구성하는데, 이는 후위 순회 결과를 역순으로 나타내면 루트 노드를 시작으로 하위 오른쪽 노드가 나타나므로 후위 순회 끝 지점에서 1씩 감소시키고 해당 노드를 기준으로 다시 앞선 작업을 반복(재귀)함으로써 최종적인 트리를 구성할 수 있게 됩니다.

 

        public void buildTree(int[] in, int[] post) {
            pIndex = in.length - 1;
            root = buildTree(in, post, 0, in.length - 1);
        }

        private Node buildTree(int[] in, int[] post, int start, int end) {
            if (start > end) {
                return null;
            }

            Node node = new Node(post[pIndex--]);

            if (start == end) {
                return node;
            }

            int mid = search(in, start, end, node.data);

            node.right = buildTree(in, post, mid + 1, end);
            node.left = buildTree(in, post, start, mid - 1);

            return node;
        }

        private int search(int[] in, int start, int end, int target) {
            for (int i = start; i <= end; i++) {
                if (in[i] == target) {
                    return i;
                }
            }

            throw new IllegalArgumentException("해당되는 값의 노드가 없습니다.");
        }

 

최종적으로 만들어진 트리에 대해 전위 순회한 결과를 출력합니다.

 

        private void preOrder(Node node) {
            if (node == null) {
                return;
            }

            System.out.print(node.data + " ");
            preOrder(node.left);
            preOrder(node.right);
        }

 

소스 코드

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

class Main {

    static class Tree {
        Node root;
        int pIndex;

        public void buildTree(int[] in, int[] post) {
            pIndex = in.length - 1;
            root = buildTree(in, post, 0, in.length - 1);
        }

        private Node buildTree(int[] in, int[] post, int start, int end) {
            if (start > end) {
                return null;
            }

            Node node = new Node(post[pIndex--]);

            if (start == end) {
                return node;
            }

            int mid = search(in, start, end, node.data);

            node.right = buildTree(in, post, mid + 1, end);
            node.left = buildTree(in, post, start, mid - 1);

            return node;
        }

        private int search(int[] in, int start, int end, int target) {
            for (int i = start; i <= end; i++) {
                if (in[i] == target) {
                    return i;
                }
            }

            throw new IllegalArgumentException("해당되는 값의 노드가 없습니다.");
        }

        public void preOrder() {
            preOrder(root);
        }

        private void preOrder(Node node) {
            if (node == null) {
                return;
            }

            System.out.print(node.data + " ");
            preOrder(node.left);
            preOrder(node.right);
        }

        static class Node {
            int data;
            Node left;
            Node right;

            public Node(int data) {
                this.data = data;
            }
        }
    }

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

        int n = Integer.parseInt(br.readLine());

        int[] in = new int[n], post = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            in[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            post[i] = Integer.parseInt(st.nextToken());
        }

        Tree tree = new Tree();
        tree.buildTree(in, post);

        tree.preOrder();
    }
}

 

참고자료

• https://www.acmicpc.net/problem/2263
• https://www.youtube.com/watch?v=kGdnFfi2uz8