[백준 2263번] 트리의 순회 - python

문제 링크

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

2263번: 트리의 순회

풀이 - 다른 블로그 참고 

전위 순회 : (정점)(왼쪽)(오른쪽)

후외순회 : (왼쪽)(오른쪽)(정점)

중위순회 : (왼쪽)(정점)(오른쪽)

중위 순회와 후위순회를 통해 트리를 구할 수 있다.

 

1. 후위 순회의 마지막 숫자는 전위 숫자의 처음 숫자이다.

후위 순회는 (왼쪽)(오른쪽)(정점), 전위 순회는 (정점)(왼쪽)(오른쪽) 이기 때문 

2. 중위 순회로 정점을 기준으로 왼쪽 서브 트리의 노드수, 오른쪽 서브 트리의 노드 수 알 수 있다. 

# https://www.acmicpc.net/problem/2263
import sys
sys.setrecursionlimit(10 **5)
input = sys.stdin.readline 

n = int(input())

inorder = list(map(int,input().split()))
post = list(map(int,input().split()))

index = [0] * (n+1)

# 정점의 인덱스 저장 -> 왼쪽 서브 트리 노드 수, 오른쪽 서브 트리 노드 수 알 수 있음 
for i in range(n):
    index[inorder[i]] = i 

def preorder(istart,iend,pstart,pend):
    # 역전 시 중단 
    if istart > iend or pstart > pend:
        return 
    # 후위 순회의 맨 마지막 정점은 전위 순회의 처음 정점 
    root = post[pend]
    # 전위 순회이므로 정점 출력 먼저 
    print(root, end = " ")
    
    # 왼쪽 서브 트리 
    left = index[root] - istart
    # 오른쪽 서브 트리
    right = iend - index[root]
    
    # 중위순회, 후위 순회의 왼쪽 서브 트리
    preorder(istart, istart + left -1 , pstart, pstart + left -1)
    # 중위순회, 후위 순회의 오른쪽 서브 트리
    preorder(iend - right +1, iend, pend-right, pend-1)
    
preorder(0,n-1,0,n-1)

- 어렵다 ㅠㅠ 반복해서 풀어보기 

 

+ 트리 순회 관련 백준 문제 

- 트리가 주어졌을 때 전위, 후위, 중위 순회 문제 : https://www.acmicpc.net/problem/1991

1991번: 트리 순회

- 전위 순회가 주어졌을 때, 후위 순회 구하는 문제 : https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

- 후위 순회, 중위 순회가 주어졌을 때, 전위 순회를 구하는 문제 : https://www.acmicpc.net/problem/2263

2263번: 트리의 순회