[BOJ]2263. 木の回り

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()メソッドは呼び出されず、時間を短縮するために利用される.

サマリ

ポストシーケンスと中シーケンスのポストシーケンスが与えられると、各ノードが有するインデックスを用いて前シーケンスのポストシーケンスを求めることができる.