[伯俊]9934完全バイナリツリー(Java)

質問リンク

もんだいぶんせき

入力

しゅつりょく

に答える

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

完全なコード

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);
        }
    }
}