[백준 2263번] 파이썬 - 트리의 순회

http://www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

 

 

# 조건

• n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다.
• 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리 오더를 구하여라

 

# 접근 방법

• 중위 순회와 후위 순회가 주어진다.
  • 중위의 경우 -> LVR
  • 후위의 경우 -> LRV
• 왼쪽 자식 노드부터 시작한다.
• 후위 순회의 가장 마지막 수 -> 루트 노드
• 루트 노드를 중위 순회에서 살펴보면 left tree와 right tree를 찾을 수 있다.
• 이 때, 정점의 인덱스를 알고 있기 때문에 왼쪽 자식의 개수, 오른쪽 자식의 개수를 알 수 있다. (중요)
  • 각 서브 트리의 루트 노드를 알기 위하여 후위 순회의 인덱스도 인자로 사용해준다.
  • 각 서브 트리의 남은 수 + 시작인덱스를 하면 루트 노드의 값을 알 수 있다.
• 이후, 재귀를 통하여 트리를 구성해주고, 전위 순회 결과 출력해주면 된다.

 

참고 - https://ca.ramel.be/114

import sys  
sys.stdin = open('input.txt')  
sys.setrecursionlimit(10**9)  
  
# 전위 순회 시작 끝 인덱스, 후위 순회 시작 끝 인덱스  
def pre_order(i_start, i_end, p_start, p_end):  
    # 역전 되면 구분할 노드가 없는 것  
    if i_start > i_end or p_start > p_end:  
        return  
    root = post_order[p_end]  
    print(root, end=' ')  
  
    left_cnt = tree[root] - i_start  
    right_cnt = i_end - tree[root]  
  
    # 왼쪽 트리  
    # 전위순회 - 시작 그대로    #            끝 인덱스는 루트 찍었으므로 -1    # 후위 순회 - 시작 그대로    #             끝 인덱스는 시작인덱스 + 왼쪽 트리 남은 수 -1    
    pre_order(i_start, tree[root]-1, p_start, p_start + left_cnt -1)  
    # 오른쪽 트리  
    # 전위순회 - 루트 노드 + 1    #            끝 인덱스는 그대로    # 후위 순회 - 시작 인덱스 => 끝인덱스 - 오른쪽 트리의 남은 노드 수    #             끝 인덱스 => 끝 인덱스 - 1    
    pre_order(tree[root]+1, i_end, p_end-right_cnt, p_end -1)  
  
N = int(input())  
in_order = [*map(int, input().split())]  
post_order = [*map(int, input().split())]  
  
tree = [0] * (N+1)  
for i in range(N):  
    # 후위 순회의 끝 값이 중위 순회의 어디 인덱스에 위치하는지 알기 위해  
    # 중위 순회의 값들의 인덱스 값을 저장    
    tree[in_order[i]] = i  
  
pre_order(0, N-1, 0, N-1)