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

    サマリ


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