1.質問

n個の頂点を持つバイナリツリーの頂点には、1からnまでの番号が重複していません.このバイナリ・ツリーのインベントリとインベントリが指定されている場合は、サブスクリプションを取得するプログラムを作成します.

せいげんじょうけん

時間:5秒
メモリ:128 MB

入力

第1行はn(1≦n≦100000)を与える.次の行はインボイスを表すn個の自然数を与え、次の行は同じように後注文を与える.

しゅつりょく

最初の行にサブスクリプションを出力します.

-キーワード

中尉巡りと後衛巡りの特徴からノードを抽出する.

時間とメモリ量をよく参考にしてください.

2.解答

この問題を読むとき、前回の問題をよく考えました.

中央値の順序には、親ノードに対して左、右の分割が表示されます.
後ろの列の順序から、親ノードは常に最後尾にあることがわかります.
この特徴により前序を求めることができる.
次のテストケースを見てみましょう.
11
8 4 2 9 5 1 10 6 3 11 7
8 4 9 5 2 10 6 11 7 3 1

後列巡回の末尾に親ノードを探し,中列を基準に区分する.

前列の順序は左側のノードの親ノードからナビゲートを開始するので、まず左側のノードの親ノードを検索します.

これで、どんなアルゴリズムを聞くかがわかります.
分割征服を利用して解決することである.
このプロセスを続けましょう.

次の左側のノードでは、親ノードは4です.
サブノードは8しか残っていないので、8は次のノードに入ります.
右側ノード9,5も同様の手順を経る.

さっきの状況なので、同じ過程を経ています.
6 10 7 11番で入ってきます

結果としてpreorderは以下のようになります.

3.ソースコード

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100001)

preorder = []
inorder = []
postorder = []

# def divide(inorder,postorder): 메모리 초과
# 	if len(inorder) == 1:
# 		preorder.append(inorder[0])
# 	elif inorder and postorder:
# 		for i in range(len(inorder)):
# 			if inorder[i] == postorder[-1]:
# 				preorder.append(postorder[-1])
# 				divide(inorder[:i],postorder[:i])
# 				divide(inorder[i+1:],postorder[i:-1])

def divide(il,ir,pl,pr):
	if ir - il != pr - pl:
		return
	if il < ir and pl < pr:
		for i in range(ir-il):
			if inorder[il+i] == postorder[pr-1]:
				preorder.append(postorder[pr-1])
				divide(il,il+i,pl,pl+i)
				divide(il+i+1,ir,pl+i,pr-1)


def solution():
	divide(0,N,0,N)
	for i in preorder:
		print(i,end=" ")

if __name__ == "__main__":
	N = int(input())
	inorder = list(map(int,input().split()))
	postorder = list(map(int,input().split()))
	solution()

注釈処理の部分はスクライブによって実現される.
論理的には同じパフォーマンスですが、メモリオーバーフローが発生します.
nは100000に達するため、メモリが過負荷になる可能性があります.
グローバル変数として宣言し、インデックス値のみを使用します.
深さの問題があるのでsys.recursonlimit(100001)を追加します.

4.後期

いつものようにしようと思っていたのに、メモリが超過していたことに気づきました.
インデックス値を超えた値に変更しようとすると、頭がかなり痛いと思います.
問題を解決した当日、頭に過負荷がかかり、翌日に解決することにした.
やはりアルゴリズムには十分な休憩が必要です.
翌日は数分もかからずに解けました.
メモリの制限に対応するために、インデックスの作成も練習する必要があるようです.