[백준] 트리

1. 문제 이해하기

• 전위 순회, 중위 순회 순서가 주어지면 후위 순회 순서를 구하는 문제이다. 예전에 동일한 문제를 풀어본 적이 있어서 어떻게 푸는지는 알았다. 근데 시간이 이렇게 오래 걸릴 줄은 몰랐다…

2. 이론 세우기

• 우선 전위 순회는 가장 앞에 있는 노드가 루트이다. 또 중위 순회는 루트를 기준으로 왼쪽은 루트의 왼쪽 자식, 오른쪽은 루트의 오른쪽 자식으로 나뉜다. 재귀 함수를 이용해 왼쪽 자식, 오른쪽 자식을 출력한 뒤 루트를 출력하는 함수를 만들면 된다.
• 처음에는 재귀 함수로 전달하는 루트 노드를 노드 번호로 했었는데, 재귀호출 시 전위 순회[후위 순회[루트번호] + 1] 이런 식의 코드가 나오게 되었고 n이 범위를 벗어나는 경우 인덱스 오류가 났다. 이후부터 머리가 너무 아파서 그냥 예외처리 대신 인덱스로 루트를 넘겨주는 식으로 코드를 짰다.

3. 이론 검증하기

• 루트 노드의 왼쪽 자식은 전위 순회에서 루트 인덱스 + 1에 존재한다. 또 루트 노드의 모든 왼쪽 자손들은 중위 순회에서 루트가 위치한 부분의 왼쪽에 위치한다.

• pre에서의 위치(인덱스)를 기준으로 루트를 선정한다.
• 오른쪽 자식은 pre에서 루트의 바로 오른쪽에 존재한다. 즉 pre[n] + 1이다.
• 왼쪽 자식은 pre에서 루트의 모든 자손(노란 네모)을 거친 이후에 등장한다. 즉 pre[n] + len(in[n] - 1)이다.
• 루트 인덱스가 n - 1보다 커지면 범위를 넘어가므로 함수를 종료한다.
• 각 재귀 함수를 호출할 때 볼 범위를 in 기준으로 넘겨준다. 즉 파란 네모를 루트로 하고 왼쪽 자손을 찾는 재귀 함수를 호출하면, 해당 함수는 in의 노란 네모 부분만을 신경쓴다는 것을 알려주는 것이다.
• 시작 인덱스와 종료 인덱스가 같아지면 리프 노드이므로 함수를 종료한다.

4. 의사코드 작성하기

**- 재귀 함수(전위 순회에서 루트의 인덱스, 시작 인덱스, 종료 인덱스)**
범위를 벗어나면 함수를 종료한다. 
리프 노드이면 현재 노드를 출력에 추가하고 종료한다. 

재귀 함수(n + 1, 시작 인덱스, in에서의 루트 위치 - 1)로 왼쪽 자식을 탐색한다. 
왼쪽 자식 개수를 센다. 
재귀 함수(n + 왼쪽 자식 개수 + 1, in에서의 루트 위치 + 1, 종료 인덱스)로 오른쪽 자식을 탐색한다. 
현재 노드를 출력에 추가하고 종료한다. 

5. 복기하기

import sys
input = sys.stdin.readline

def postOrder(n, si, ei):
    if si > ei or n >= N:
        return
    if si == ei:
        result.append(p[n])
        return
    postOrder(n + 1, si, inO[p[n]] - 1) # 왼쪽 자식 탐색
    leftCnt = inO[p[n]] - si
    postOrder(n + leftCnt + 1, inO[p[n]] + 1, ei) # 오른쪽 자식 탐색
    result.append(p[n])
    return

def solution():
    global N, preO, inO, visited, p, i, result
    N = int(input())
    p = list(map(int, input().split()))
    i = list(map(int, input().split()))
    preO = dict()
    inO = dict()
    for x in range(N):
        preO[p[x]] = x
        inO[i[x]] = x

    visited = [False] * (N + 1)
    result = []
    postOrder(0, 0, N - 1)
    print(*result)

t = int(input())
for _ in range(t):
    solution()

• 그림으로 그려보는 것을 계속 연습해야겠다. 특히 인덱스와 관련된 문제는 한끝차이로 오류가 발생하는 경우가 많으니까 더 세심하게 설계해야 할 것 같다.