[ALGOSPOT] 알고스팟 TRAVERSAL 트리 순회 순서 변경(Python)

www.algospot.com

[ALGOSPOT] 알고스팟 TRAVERSAL 트리 순회 순서 변경

(Python)

(글쓴날 : 2020.06.01)

 

---

* ALGOSPOT, 알고스팟 TRAVERSAL 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 TRAVERSAL 트리 순회 순서 변경

---

1) 문제

문제 링크 : https://algospot.com/judge/problem/read/TRAVERSAL

algospot.com :: TRAVERSAL

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

전위 순회 출력값과, 중위 순회 출력값이 주어질 때, 해당 트리의 후위 순회 출력값을 구하는 문제입니다.

 

저의 경우, Python을 사용했습니다.

먼저, 전위 순회는 항상 첫 번째로 루트 노드를 출력하는 특징을 이용해 루트 노드의 값을 찾았습니다.

그 후, 찾은 루트 노드의 값을 중위 순회 출력값에서 찾아 해당 인덱스를 기준으로 트리를 재귀적으로 분리하였고, 더 이상 분리할 수 없어 회귀를 시작할 때, 재귀 호출을 할 때마다 찾았던 루트 노드의 값을 출력하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def printPostorder(preorder, inorder):
    if not len(preorder):
        return
 
    root = preorder[0]
    mid = inorder.index(root)
 
    printPostorder(preorder[1:mid + 1], inorder[0:mid])
    printPostorder(preorder[mid + 1:len(preorder)], inorder[mid + 1:len(preorder)])
 
    print(root, end=" ")
 
 
C = int(input())
for _ in range(C):
    N = int(input())
 
    preorder = list(map(int, input().split()))
    inorder = list(map(int, input().split()))
 
    printPostorder(preorder, inorder)
    print()

---