問題の説明

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

尚根は町のすべてのビルに入って、入る順番に番号を紙に書いた.韓国に帰ってきた尚根は町の様子を描こうとしたが、覚えていないので失敗.でも、どんな順番で町を訪れたか覚えています.

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

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

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

現在ビルに入っており、右側のサブアイテムがあれば右側のサブアイテムに移動します.

現在のビルと左、右サブシステムのすべてのビルにアクセスした場合は、親ノードに移動します.

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

提问链接

完全なコード

def solution(start, end, level):
    if start == end:
        ans[level].append(tree[start])
        return

    center = (start + end) // 2
    ans[level].append(tree[center])
    solution(start, center-1, level+1)
    solution(center+1, end, level+1)

k = int(input())
tree = list(map(int, input().split()))
ln = len(tree)
ans = [[] for _ in range(k)]

solution(0, ln-1, 0)
for a in ans:
    print(*a)

解決策

巡回の順序では,真ん中の数が木の根となることを考えるべきである.そして、その基準で左右に分けると、真ん中の数が再び子木の根になります.並べ替えを合わせるような感じで、左右に切って解けばいいです.