白駿2263号:木の巡り
4844 ワード
問題解決の考え方
一般ツリー遍歴の概念については、次の投稿-https://hongku.tistory.com/160を参照してください.
後方ループ(Postorderワイヤ)から,最後にルートノードのデータであることが容易に分かる.
これにより、中位遍歴でルートノードを見つけることができ、中位遍歴の特性で左から右に進むため、ルートノードによって左から右のサブツリーに分けることができる.(左図参照)
後列巡りの結果に分割されたsubtreeが見つかれば,それらも同様に縛られていることが確認できる.このグループでは、最後に到着したデータもルートノードに相当します.(右図参照)
この過程を繰り返し、中尉巡りと後衛巡りの結果を分けると、木全体が明らかになる.
✔正解コード
import sys
sys.setrecursionlimit(10**6) # 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이므로 필수
n = int(sys.stdin.readline())
inOrder = list(map(int, sys.stdin.readline().split()))
postOrder = list(map(int, sys.stdin.readline().split()))
directInOrder = [-1]*(n+1)
for i in range(n):
directInOrder[inOrder[i]] = i
def fillTree(stIndx_i, edIndx_i, stIndx_p, edIndx_p, currentRoot):
currentRoot['data'] = postOrder[edIndx_p]
mid = directInOrder[postOrder[edIndx_p]]
if stIndx_i < mid:
leftRoot = {}
currentRoot['left'] = leftRoot
fillTree(stIndx_i, mid-1, stIndx_p, stIndx_p+(mid-stIndx_i-1), leftRoot)
if mid < edIndx_i:
rightRoot = {}
currentRoot['right'] = rightRoot
fillTree(mid+1, edIndx_i, edIndx_p-(edIndx_i-mid), edIndx_p-1, rightRoot)
def preOrder(currentRoot):
print("{} ".format(currentRoot['data']), end="")
if 'left' in currentRoot:
preOrder(currentRoot['left'])
if 'right' in currentRoot:
preOrder(currentRoot['right'])
ultimateRoot = {}
fillTree(0, n-1, 0, n-1, ultimateRoot)
preOrder(ultimateRoot)
print()
定義
InOrder配列を参照するたびに時間の複雑さが増し、以下の処理により、inOrderの各データがいくつかのインデックスにあることを一度に理解できます.
directInOrder = [-1]*(n+1)
for i in range(n):
directInOrder[inOrder[i]] = i ツリーの関数を表す再帰呼び出し.4つの変数で配列を分割し、ツリー全体を復元します.
def fillTree(stIndx_i, edIndx_i, stIndx_p, edIndx_p, currentRoot):
# stIndx_i, edIndx_i: inOrder 배열에서 살펴볼 곳의 시작점과 끝점
# stIndx_p, edIndx_p: postOrder 배열에서 살펴볼 곳의 시작점과 끝점
currentRoot['data'] = postOrder[edIndx_p]
mid = directInOrder[postOrder[edIndx_p]]
if stIndx_i < mid:
leftRoot = {}
currentRoot['left'] = leftRoot
fillTree(stIndx_i, mid-1, stIndx_p, stIndx_p+(mid-stIndx_i-1), leftRoot)
if mid < edIndx_i:
rightRoot = {}
currentRoot['right'] = rightRoot
fillTree(mid+1, edIndx_i, edIndx_p-(edIndx_i-mid), edIndx_p-1, rightRoot)また、ルートノードからサブツリーのルートノードに下に移動し、ツリー全体を照らすため、現在のルートノードも一緒に移行します.
また、現在のルートノードの値がInOrderのいくつ目のインデックスにあるかを決定することにより、midという変数に入れる.
このとき、inOrderの次に表示する部分は現在のルートノードの左側であるため、stindx iとmid-1が渡されます.
また、次のPostOrderで表示する部分は、以前に表示した開始点から始まり、以下に示すようにinOrderで表示する部分のサイズ(mid-1-stIndx i)に渡されます.
このとき、inOrderの次の部分が現在のルートノードの右側にあるため、mid+1とedIndx iが渡されます.
また、次のPostOrderで表示する部分は、以下に示すように、表示される端点から1つ減算されたedIndx p-1から始まり、inOrderで表示される部分の大きさに従って転送されます.
再帰電位は巡回し,データの関数を順次出力する.ディクショナリにキー値があるかどうかを確認すると、次の処理が行われます.
def preOrder(currentRoot):
print("{} ".format(currentRoot['data']), end="")
if 'left' in currentRoot:
preOrder(currentRoot['left'])
if 'right' in currentRoot:
preOrder(currentRoot['right'])まず、配列全体を表示して開始するので、0とn-1はスキップされます.さらに、ルートノードであるdictionaryを宣言し、それをfillTree関数に渡してTreeを完了します.このルートノードをpreOrder関数に入れ、正解を出力します.
ultimateRoot = {}
fillTree(0, n-1, 0, n-1, ultimateRoot)
preOrder(ultimateRoot)
print()
最初は上記の原理が完全に実現されていなかったため,エラーはsetRecursionLimit法を用いてRecursionErrorが容易に解決した.
質問に対する反例:https://bingorithm.tistory.com/5
Reference
この問題について(白駿2263号:木の巡り), 我々は、より多くの情報をここで見つけました https://velog.io/@dlehdtjq00/백준-2263번-트리의-순회テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol