[백준] 9934 완전 이진 트리(Java)

문제링크

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

문제분석

• 높이가 k인 완전 이진트리 => 총 (2^k-1)개의 노드
• 이진 트리의 중위순회 결과(빌딩 번호)가 주어진다.
• 각 레벨에 있는 빌딩 번호는?

입력

• 완전 이진 트리의 깊이 K (1 ≤ K ≤ 10)
• 트리의 중위 순회 결과(상근이가 방문한 빌딩 번호들)
• 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2^k)에 포함된다.

출력

• 총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다. 출력은 왼쪽에서부터 오른쪽 순서대로 출력한다.

풀이

• Node를 표현할 클래스 선언

class Node{
    int num;
    //자식노드의 주소를 멤벼 변수로 갖는다.
    Node leftChild;
    Node rightChild;
}

• 높이가 k인 완전 이진 트리를 만든다.
• 만들어진 이진 트리를 중위 순회하며 다음 작업을 한다.
  • 입력된 번호를 해당 노드에 저장한다.
  • 해당 Level에 현재 node의 번호 저장

전체 코드

import java.util.*;

class Node{
    int num;
    //자식노드의 주소를 멤벼 변수로 갖는다.
    Node leftChild;
    Node rightChild;

    public Node(Node leftChild, Node rightChild) {
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}

public class Main {
    static ArrayList<Integer>[] answer; //출력에 사용할 변수
    static int[] visit; //입력된 빌딩 번호를 저장할 변수
    static int idx = 0; //visit의 index. Node에 빌딩 번호를 넣을 때 사용
    static int nodeSize; //노드들의 개수

    public static void main(String[] args) {
        //입력을 받는다.
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        answer = new ArrayList[k];
        for(int i=0; i<k; i++){
            answer[i] = new ArrayList<>();
        }
        nodeSize = (int)Math.pow(2, k)-1;
        visit = new int[nodeSize];
        for(int i=0; i<nodeSize; i++) visit[i] = scanner.nextInt();

        //높이가 k인 완전 이진 트리 생성
        //루트 노드를 선언하고, 큐에 넣는다.
        Node root = new Node(null, null);
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        for(int i=0; i<k-1; i++){
            //현재 Level에 있는 노드의 개수
            int queueSize = queue.size();

            //현재 Level의 Node들에 대해
            for(int j=0; j<queueSize; j++){
                Node parent = queue.poll();

                //자식 Node를 선언 후 부모와 연결해준다.
                Node child1 = new Node(null, null);
                Node child2 = new Node(null, null);
                parent.leftChild = child1;
                parent.rightChild = child2;

                //자식 노드들이 다음 Level의 Node들이므로, queue에 넣어준다.
                queue.offer(child1); queue.offer(child2);
            }
        }

        //중위 순회
        inorder(root, 0);

        //결과 출력
        for (ArrayList<Integer> levelNodes : answer) {
            for (Integer levelNode : levelNodes) {
                System.out.print(levelNode+" ");
            }
            System.out.println();
        }
    }

    private static void inorder(Node node, int level) {
        //왼쪽 자식을 먼저 방문
        if (node.leftChild != null) {
            inorder(node.leftChild, level+1);
        }

        //현재 노드의 num에 빌딩 번호를 저장
        node.num = visit[idx++];
        //현재 level에 빌딩번호 저장
        answer[level].add(node.num);

        //오른쪽 자식은 가장 나중에 방문
        if(node.rightChild!=null){
            inorder(node.rightChild, level+1);
        }
    }
}