[백준/파이썬] 4256 트리

문제

4256번: 트리 (acmicpc.net)

4256번: 트리

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 줄에는 BT를 전위 순회한 결과, 그 다음 줄에는 중위 순회한 결과가 주어진다. 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어진다.

출력

각 테스트 케이스마다 후위 순회한 결과를 출력 한다.

 

예제 입력

2
4
3 2 1 4
2 3 4 1
8
3 6 5 4 8 7 1 2
5 6 8 4 3 1 2 7

예제 출력

2 4 1 3
5 8 4 6 2 1 7 3

소스코드

import sys
 
 
def toPostorder(preorder, inorder):
    if len(preorder) == 0:
        return
    elif len(preorder) == 1:
        print(preorder[0], end=' ')
        return
    elif len(preorder) == 2:
        print(preorder[1], preorder[0], end=' ')
        return
 
    root_idx = inorder.index(preorder[0])
 
    left_in = inorder[0:root_idx]
    left_pre = preorder[1:1+len(left_in)]
    toPostorder(left_pre, left_in)
 
    right_in = inorder[root_idx+1:]
    right_pre = preorder[len(left_pre)+1:]
   toPostorder(right_pre, right_in)
    print(preorder[0], end=' ')
 
 
T = int(sys.stdin.readline().strip())
 
for t in range(T):
    N = int(sys.stdin.readline().strip())
    preorder = list(map(int, sys.stdin.readline().strip().split()))
    inorder = list(map(int, sys.stdin.readline().strip().split()))
 
    toPostorder(preorder, inorder)
    print()

전위순회한 결과의 맨 앞이 트리 전체의 루트가 되고,

루트를 기준으로 중위순회한 결과의 왼쪽은 왼쪽 서브트리, 오른쪽 서브트리가 된다.

문제에 있는 이 트리로 설명을 해보면,

루트 3을 기준으로 빨간색이 왼쪽 서브 트리, 초록색이 오른쪽 서브 트리인데,

여기서 첫번째가 전위순회, 두번째가 중위순회 결과에 서브트리를 표시한것이다. 

후위순회에서 루트는 마지막에 출력하므로, 3은 맨 끝으로 간다. 그리고 왼쪽 서브트리가 먼저 출력되는데, 왼쪽 서브트리의 중위순회, 전위순회를 다시 함수에 넣고 실행한다.

이 다음은 6 5 4 8, 5 6 8 4가 함수의 인자로 들어가는 것이다. 즉 3을 기준으로 왼쪽 서브트리의 순회 결과이다. 

왼쪽 서브트리를 출력하고, 같은 원리로, 오른쪽 서브트리를 출력한다.

 

이렇게 재귀적으로 실행 하다보면 서브트리의 노드 개수가 하나 이거나 두개일 경우가 나오는데, 이때는 중위 순회 결과를 그대로 출력하면 된다.

마지막으로 root를 출력하면 후위 순회 결과가 된다.