[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

1. 현재 서브 트리의 루트는 postorder[pe_idx]이며 이를 출력한다.

   

2. 현재 서브 트리의 루트가 inorder 리스트에서 갖는 인덱스를 찾는다. 이 인덱스를 기준으로 inorder 리스트에서 좌측 자식 노드와 우측 자식 노드가 결정된다.

   

3. inorder 리스트에서 좌측 자식 노드와 우측 자식 노드의 개수를 구할 수 있다. 이렇게 구한 자식 노드의 개수left_range, right_range를 이용해 서브 트리에 해당하는 postorder 리스트 인덱스 범위를 구할 수 있다.

   

4. 서브 트리에서 이를 반복한다.

   

문제

시간 초과.

⭕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() 메서드를 호출하는 대신 이를 이용해 시간을 단축했다.

요약

후위 순회 순서와 중위 순휘 순서가 주어졌을 때 각 노드가 갖는 인덱스를 이용해 전위 순휘 순서를 구할 수 있다.