[伯俊][9934号:完全二進樹]-Slover 1

🎈質問する

質問リンク
サンゲンはスロベニアの都市DonjiAndrijevciを旅行しています.この町の道路は深さKの完全な木を構成している.深さKの完全二叉木は2 K−1ノードからなる.(下図)各ノードには、その上にあるビルの番号が付いています.また、最終級を除いて、すべての家には左と右の子供がいます.
尚根は町のすべてのビルに入って、入る順番に番号を紙に書いた.韓国に帰ってきた尚根は町の様子を描こうとしたが、覚えていないので失敗.でも、どんな順番で町を訪れたか覚えています.

最初、尚根は木の根元にあるビルの前に立っていた.

現在のビルの左側のサブビルに入っていない場合は、左側のサブビルに移動します.

現在のノードに左サブノードがない場合、または左サブノードのビルに入った場合、現在のノードのビルに入り、紙に番号を付けます.

は現在ビルに入っており、右側の子供がいれば右側の子供に移動します.

現在のビルと左、右の2つのサブビルを訪問した場合は、親ノードに移動します.

左図に示す村であれば、上根は2-1-3の順でビルに入る可能性があり、右図は1-6-4-3-5-2-7の順で入る.尚根が紙に書いたすべての順序が与えられている場合は、プログラムを作成し、各階の番号を求めます.

🎈入力

第1行はK(1≦K≦10)を与える.
2行目は上根訪問のビル番号の順に与えられます.すべてのビルの番号は重複せず、区間[1,2 Kに含まれる.

🎈しゅつりょく

K行で正解を出力します.i行目は、iのレベルのビルの番号を出力します.出力は左から右へ順次出力されます.

🎈方法

ツリーの作成
1.再帰関数によりツリーを生成します.
2.中間値は親ノードです.親ノードを基準として、左と右も同じで、左の値の中間の値は親ノードの左の子ノードであり、右の値の中間の値は親ノードの右の子ノードである.このように,リーフノードも再帰関数によりツリーを完成させる.
しゅつりょくツリー

キューで対応する深さ(深さ)を求めて出力します.

🎈コード#コード#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    static int K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(br.readLine()); // depth (깊이)
        int N = (int)Math.pow(2,K)-1; // 노드의 개수
        String[] str = br.readLine().split(" ");
        List<Integer> list = new ArrayList<>();

        for(int i=0; i<N; i++){
            list.add(Integer.parseInt(str[i]));
        }
        Node root = buildTree(list, 0, list.size()-1);
        printTree(root);
    }
    static class Node{
        int data;
        Node left;
        Node right;

        Node(int data){
            this.data = data;
        }
    }
    static Node buildTree(List<Integer> list, int start, int end){
        if(start > end){
            return null;
        }
        int mid = (start+end)/2;
        Node node = new Node(list.get(mid));

        if(start==end){
            return node;
        }
        node.left = buildTree(list,start, mid-1);
        node.right = buildTree(list,mid+1, end);

        return node;
    }
    static void printTree(Node root){
        StringBuilder sb = new StringBuilder();

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                Node node = queue.poll();
                sb.append(node.data).append(" ");
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            sb.append('\n');
        }

        System.out.println(sb.toString());
    }
}