Tree 02完全バイナリツリー(9934)

質問する

サンゲンはスロベニアの都市DonjiAndrijevciを旅行しています.この町の道路は深さKの完全な木を構成している.深さKの完全二叉木は2 K−1ノードからなる.(下図)各ノードには、その上にあるビルの番号が付いています.また、最終級を除いて、すべての家には左と右の子供がいます.

深さ2と3の完全なバイナリツリー
尚根は町のすべてのビルに入って、入る順番に番号を紙に書いた.韓国に帰ってきた尚根は町の様子を描こうとしたが、覚えていないので失敗.でも、どんな順番で町を訪れたか覚えています.
最初、尚根は木の根元にあるビルの前に立っていた.
現在のビルの左側のサブビルにまだ入っていない場合は、左側のサブビルに移動します.
現在のノードに左のサブノードがない場合、または左のサブノードのビルに入っている場合は、現在のノードのビルに入り、紙に番号を付けます.
現在ビルに入っており、右側のサブアイテムがあれば右側のサブアイテムに移動します.
現在のビルと左、右サブシステムのすべてのビルにアクセスした場合は、親ノードに移動します.
左図に示す村であれば、上根は2-1-3の順でビルに入る可能性があり、右図は1-6-4-3-5-2-7の順で入る.尚根が紙に書いたすべての順序が与えられている場合は、プログラムを作成し、各階の番号を求めます.

入力

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

しゅつりょく

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

に答える

BFSによる

の解決

は配列され、中間値はルートであり、ルートを基準に左、右の2つのサブルートに分けられる.

makeTree関数によってサブツリーと現在の深さが伝達されます.

コード#コード#

import sys
sys.stdin = open("input.txt","rt")

K = int(input())

_input = list(map(int,input().split()))
tree = [[] for _ in range(K)]

def makeTree(arr, x):
    mid = (len(arr)//2)
    tree[x].append(arr[mid])
    if len(arr) == 1:
        return
    makeTree(arr[:mid], x+1)
    makeTree(arr[mid+1:], x+1)

makeTree(_input, 0)
for i in range(K):
    print(*tree[i])

学識

コメント