트리의 순회

이진트리에 관한 문제다. In-Order, Post-Order 그리고 Pre-Order 관련한 내용은 이를 다루고 있는 다른 블로그도 많기 때문에 다루지 않겠다. 한 번 검색해보자.

아래의 예제를 활용해 문제를 풀어볼 것이다.

위와 같은 트리가 존재할 때, In-Order, Post-Order 그리고 Pre-Order는 다음과 같다. In-Order와 Post-Order를 어떻게 활용할 수 있을까?

• 이진 트리의 가장 위에 위치하는 노드가 Post-Order에서 가장 마지막에 위치한다.
• In-Order에서 이진 트리의 가장 위에 위치하는 노드를 기준으로 양옆 가지로 갈라지게 된다.

위의 두가지 특징을 사용하면 In-Order와 Post-Order를 활용해 트리의 모양을 유추할 수 있다. 아래의 그림을 보며 이해해보자.

• 주어진 Post-Order에서 3이 가장 마지막에 위치함으로, 이진트리의 최상단에 3이 위치한다는 사실을 알 수 있다.
• In-Order에서는 3을 기준으로 왼쪽가지와 오른쪽 가지를 이루는 수로 나뉜다. 따라서, ‘8 1 9 2 10 5’는 3의 왼쪽 아래에 위치하고, ‘6 4 7’은 3의 오른쪽 아래에 위치한다는 것을 알 수 있다.
• 이 과정을 재귀함수를 활용해 하위 노드의 개수가 1개 이하가 될 때 까지 반복한다.

Plus

문제를 풀면서 메모리 초과와 시간초과 둘다 발생해 이를 힘겹게 해결했다.

재귀함수를 사용했고, 함수의 인자로 Post-Order, In-Order 리스트를 넘기도록 했더니 메모리 초과가 발생했다. 리스트 자체를 인자로 넘기는 것이 아니라, 해당 리스트 조각(?)이 문제 입력으로 주어진 리스트의 어디에 위치하는지 인덱스만 넘기면 공간복잡도를 줄일 수 있다.

find_pre(p_left, p_right, i_left, i_right)

두번째로, 매번 Post-Order의 가장 마지막에 위치하는 숫자의 In-Order에서의 위치를 index함수를 사용해 탐색해서 시간 초과가 발생했다. In-Order를 입력받은 후, In-Order의 값들이 몇 번째 인덱스에 위치하는지 미리 저장해두는 방식으로 이를 해결했다. 이 방법은 다른 블로그를 참고했습니다.

in_location = list(0 for _ in range(n+1))
for i in range(n):
    in_location[inOrder[i]] = i

CODE

import sys
read = sys.stdin.readline
sys.setrecursionlimit(1000000)

n = int(read())
inOrder = list(map(int, read().split()))
#특정 원소의 인덱스를 바로바로 찾아내기 위한 리스트
#다른 분의 블로그를 참고해 작성한 코드입니다.
in_location = list(0 for _ in range(n+1))
for i in range(n):
    in_location[inOrder[i]] = i

postOrder = list(map(int, read().split()))
preOrder = []


def find_pre(p_left, p_right, i_left, i_right):
    if p_right-p_left == 0:
        return
    elif p_right-p_left == 1:
        preOrder.append(postOrder[p_left])
        return
    node = postOrder[p_right-1]
    preOrder.append(node)
    node_i = in_location[node]

    find_pre(p_left, p_left-i_left+node_i, i_left, node_i)
    find_pre(node_i+p_right-i_right, p_right-1, node_i+1, i_right)


find_pre(0, n, 0, n)
print(*preOrder)

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]