[BOJ]2263. 木の回り
13891 ワード
2263、木の巡り
後列順でサブツリーのルート頂点を探し出し,左サブノードと右サブノードを中列順で判別する.各リストのインデックスを使用して、サブツリーの範囲を求めることができます.
次のツリーがあるとします.
ツリーの入力値とそれによって生成された
現在のサブツリーのルートは
現在のサブツリーのルートが
サブツリーでこの操作を繰り返します.
タイムアウト.
ノード番号と対応するインデックスは、それぞれ
ポストシーケンスと中シーケンスのポストシーケンスが与えられると、各ノードが有するインデックスを用いて前シーケンスのポストシーケンスを求めることができる.
❌code1
import sys
sys.setrecursionlimit(100000)
def preorder(ps_idx, pe_idx, is_idx, ie_idx):
"""
:param ps_idx: postorder start index
:param pe_idx: postorder end index
:param is_idx: inorder start index
:param ie_idx: inorder end index
"""
print(postorder[pe_idx], end=' ')
if ps_idx == pe_idx: # 리프노드 도달
return
# 현재 서브 트리의 루트는 postorder[pe_idx]
# 서브 트리의 루트가 inorder 리스트에서 갖는 인덱스 값을 찾음
inorder_root_idx = inorder.index(postorder[pe_idx])
# inorder 리스트에서 현재 서브 트리의 좌측 자식 노드 개수와 우측 자식 노드 개수
left_range = inorder_root_idx - is_idx - 1
right_range = ie_idx - inorder_root_idx - 1
# 다음 서브 트리에 해당하는 postorder 리스트와 inorder 리스트의 범위를 넘김
if 0 <= left_range:
preorder(ps_idx, ps_idx + left_range, is_idx, inorder_root_idx - 1)
if 0 <= right_range:
preorder(pe_idx - 1 - right_range, pe_idx - 1, inorder_root_idx + 1, ie_idx)
N = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))
postorder = list(map(int, sys.stdin.readline().split()))
preorder(0, N - 1, 0, N - 1)
試す
後列順でサブツリーのルート頂点を探し出し,左サブノードと右サブノードを中列順で判別する.各リストのインデックスを使用して、サブツリーの範囲を求めることができます.
次のツリーがあるとします.
ツリーの入力値とそれによって生成された
inorder
のリスト、postorder
のリストは以下の通りである.12
7 4 8 2 5 9 1 6 11 10 12 3
7 8 4 9 5 2 11 12 10 6 3 1
現在のサブツリーのルートは
postorder[pe_idx]
であり、出力されます.現在のサブツリーのルートが
inorder
リストにあるインデックスを検索します.このインデックスを基準として、inorder
リストにおいて、左サブノードおよび右サブノードが決定される.inorder
リストから左側サブノードと右側サブノードの個数を求めることができる.求めるサブノードの個数left_range
、right_range
を用いて、サブツリーに対応するpostorder
リストインデックス範囲を求めることができる.サブツリーでこの操作を繰り返します.
質問する
タイムアウト.
⭕code2
import sys
sys.setrecursionlimit(200000)
def preorder(ps_idx, pe_idx, is_idx, ie_idx):
"""
:param ps_idx: postorder start index
:param pe_idx: postorder end index
:param is_idx: inorder start index
:param ie_idx: inorder end index
"""
print(postorder[pe_idx], end=' ')
if ps_idx == pe_idx: # 리프노드 도달
return
# 현재 서브 트리의 루트는 postorder[pe_idx]
# 서브 트리의 루트가 inorder 리스트에서 갖는 인덱스 값을 찾음
inorder_root_idx = inorder_index_dict[postorder[pe_idx]]
# inorder 리스트에서 현재 서브 트리의 좌측 자식 노드 개수와 우측 자식 노드 개수
left_range = inorder_root_idx - is_idx - 1
right_range = ie_idx - inorder_root_idx - 1
# 다음 서브 트리에 해당하는 postorder 리스트와 inorder 리스트의 범위를 넘김
if 0 <= left_range:
preorder(ps_idx, ps_idx + left_range, is_idx, inorder_root_idx - 1)
if 0 <= right_range:
preorder(pe_idx - 1 - right_range, pe_idx - 1, inorder_root_idx + 1, ie_idx)
N = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))
inorder_index_dict = {} # 노드 번호와 그에 해당하는 인덱스 저장
for index, value in enumerate(inorder):
inorder_index_dict[value] = index
postorder = list(map(int, sys.stdin.readline().split()))
preorder(0, N - 1, 0, N - 1)
試す
ノード番号と対応するインデックスは、それぞれ
inorder_index_dict
ディレクトリに格納されます.inorder
リストから所望の頂点番号のインデックスを取得する場合、.index()
メソッドは呼び出されず、時間を短縮するために利用される.サマリ
ポストシーケンスと中シーケンスのポストシーケンスが与えられると、各ノードが有するインデックスを用いて前シーケンスのポストシーケンスを求めることができる.
Reference
この問題について([BOJ]2263. 木の回り), 我々は、より多くの情報をここで見つけました https://velog.io/@alexuh/boj2263テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol