파이썬 백준 4256 트리

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
 
testcase = int(input())
for x in range(testcase) : 
    n = int(input())
    preo = list(map(int, input().split()))
    ino = list(map(int, input().split()))
    ans = []
    def DAC(pleft, ileft, len) : 
        if len == 1 : 
            ans.append(preo[pleft])
        else : 
            root = preo[pleft]
            for i in range(len) : 
                if ino[ileft + i] == root : 
                    break
            if i != 0 : 
                DAC(pleft + 1, ileft, i)
            if len - i - 1 != 0 : 
                DAC(pleft + i + 1, ileft + i + 1, len - i - 1)
            ans.append(root)
    DAC(0, 0, n)
    print(*ans)

IDEA

이분트리는 루트를 기준으로 왼쪽 트리와 오른쪽 트리로 쪼개며 재귀하는 것을 반복할 수 있다.

재귀를 반복하며 트리의 길이가 1이 되었다면 자명해를 쉽게 구할 수 있다.

 

line 5 ~ 10

인풋을 받고 필요한 변수를 선언한다.

 

line 11 ~ 13

트리를 크기 1까지 분할하여 분할정복하는 함수 DAC를 정의한다.

재귀함수가 다루는 부분트리가 전체 트리에서 어디부터 어디까지인지 알려주는 변수를 인풋으로 받는다.

pleft(preorder list에서의 부분트리 시작점)

ileft(inorder list에서의 부분트리 시작점)

len(부분트리의 길이)

len이 1이라면 분할정복의 최소단위까지 도달한 것이므로 자신을 ans에 기록하고 마친다.

 

line 14 ~ 22

트리의 루트는 preorder list의 [0]이다. 그리고 그것을 inorder list에서 찾는다.

inorder list에서 루트의 왼쪽은 왼쪽 트리, 루트의 오른쪽은 오른쪽 트리이다.

왼쪽 트리의 길이는 inorder list에서의 루트의 idx i이고. 오른쪽 트리의 길이는 전체 트리 길이에서 i+1을 뺀 것이다.

즉, 왼쪽 오른쪽 각 트리가 전체 트리의 어디부터 어디까지인지 알게 됐으므로, 두 트리에 대해 재귀한다.

 

line 23 ~ 25

2개로 분기하는 재귀함수가 모두 실행을 마쳤다면, 이 트리에서 루트를 제외한 모든 노드는 ans에 기록되었다.

이제 루트를 출력할 차례이므로(후위 순회) 루트를 출력하고 재귀를 마친다.

위의 기능을 가진 재귀함수를 전체 트리에서 실행한 뒤 정답을 출력한다.