バージン解答-完全バイナリツリー9934号

📜 問題を理解する
サンゲンはスロベニアの都市DonjiAndrijevciを旅行しています.この町の道路は深さKの完全な木を構成している.深さKの完全二叉木は2 K−1ノードからなる.(下図)各ノードには、その上にあるビルの番号が付いています.また、最終級を除いて、すべての家には左と右の子供がいます.
尚根は町のすべてのビルに入って、入る順番に番号を紙に書いた.韓国に帰ってきた尚根は町の様子を描こうとしたが、覚えていないので失敗.でも、どんな順番で町を訪れたか覚えています.
最初、尚根は木の根元にあるビルの前に立っていた.
現在のビルの左側のサブビルにまだ入っていない場合は、左側のサブビルに移動します.
現在のノードに左のサブノードがない場合、または左のサブノードのビルに入っている場合は、現在のノードのビルに入り、紙に番号を付けます.
現在ビルに入っており、右側のサブアイテムがあれば右側のサブアイテムに移動します.
現在のビルと左、右サブシステムのすべてのビルにアクセスした場合は、親ノードに移動します.
左図に示す村であれば、上根は2-1-3の順でビルに入る可能性があり、右図は1-6-4-3-5-2-7の順で入る.尚根が紙に書いたすべての順序が与えられている場合は、プログラムを作成し、各階の番号を求めます.
💡 問題の再定義
バイナリツリーのノードが指定されている場合、各レベルの番号が出力されます.
▼▼▼計画作成
バイナリツリーのノードをバイナリ検索として再帰的に検索し、中間値を保存し、メイン関数に順次出力すればよい.
異なるレベルの中間値を格納するためにディックバッテリを使用した.
💻 計画の実行

def binary_search(sub_tree, _k, _tree_dict):
    mid_index = len(sub_tree) // 2
    tree_dict[_k].append(sub_tree[mid_index])
    if _k > 1:
        _k -= 1
        binary_search(sub_tree[0:mid_index], _k, _tree_dict)
        binary_search(sub_tree[mid_index+1:], _k, _tree_dict)


if __name__ == '__main__':
    k = int(input())
    tree_dict = dict()
    tree = list(map(int, input().split()))
    for i in range(1, k+1):
        tree_dict[i] = list()
    binary_search(tree, k, tree_dict)

    for i in range(k, 0, -1):
        print(*tree_dict[i], sep=' ')

🤔 振り返る
バイナリツリーのノードが与えられた場合、ツリーの再作成を初めて試みたようです.実現は難しくないが、実現は難しいようだ.