BaekJoon 2263번 : 트리의 순회 (python)

BaekJoon 2263번 : 트리의 순회 (G1 32.695%)

트리의 순회 문제

post_order와 in_order를 통해 pre_order를 알아내는 문제이다.

• 중위 순회와 후위 순회를 보았을 때 각각의 특징이 있고 두 특징을 엮어낼 수가 있다. 후위 순회는 최상위 루트를 맨 마지막에 방문하게 되고 중위 순회는 왼쪽, 루트, 오른쪽 순으로 방문하게 된다.
• 여기서 후위 순회의 맨 마지막 원소는 루트 노드가 되고 해당 중위 순회에서 해당 루트노드를 기준으로 왼쪽은 왼쪽 서브 트리, 오른쪽은 오른쪽 서브 트리로 자동으로 구분이 된다.
• 이때 중위 순회에서
  왼쪽 서브 트리의 범위는 [시작 인덱스, (시작인덱스 + 왼쪽 서브 트리의 노드 수 -1)]이 되고
  오른쪽 서브 트리의 범위는 [끝 인덱스 - 오른쪽 서브 트리의 수 +1, 끝 인덱스]로 재귀가 되게 된다.
• 동시에 후위 순회의
  왼쪽 서브 트리의 범위는 [시작 인덱스, (시작인덱스 + 왼쪽 서브 트리의 노드 수 -1)]이 되고 오른쪽 서브 트리의 범위는 [끝 인덱스 - 오른쪽 서브 트리의 수, 끝 인덱스 -1]이 되게 된다.
• 해당 재귀를 식으로 표현하기 위해 필요한 중위 순회에서 루트 노드의 인덱스를 구해주는 작업을 해주고 전위 순회를 해야하기 때문에 (루트)(왼쪽)(오른쪽) 순으로 재귀를 진행하며 출력해준다.

느낀점

inorder, postorder의 특징을 통해 preorder를 알아낼 수 있다는 부분이 매우 신기했던 문제였다. 다른 분들도 어렵게 푸신 것 같아 다들 어렵게 느꼈겠구나 라는 생각이 들었지만 아직도 재귀의 규칙이 어렵게 느껴지는 것 같다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def preorder(ins, ine, posts, poste) :
    if ins > ine or posts > poste :
        return
    
    root = postorder[poste]
    print(root, end =' ')

    root_index = node_index[root]
    left_node = root_index - ins
    right_node = ine - root_index
    
    #좌측 노드
    preorder(ins, ins + left_node - 1, posts,posts + left_node - 1)
    #우측 노드
    preorder(ine - right_node + 1, ine, poste - right_node, poste - 1)

n = int(input())
inorder = list(map(int,input().split()))
postorder = list(map(int,input().split()))
node_index = [0]*(n+1)

for i, v in enumerate(inorder) :
    node_index[v] = i

preorder(0,n-1,0,n-1)