Baekjoon Online Judge 4256번 파이썬. 분할정복.

문제 링크
https://www.acmicpc.net/problem/4256

4256번: 트리

전위순회한 결과의 맨 앞 노드는 전체 트리의 루트이다.
중위순회한 결과에서 전체 트리의 루트를 기준으로 왼쪽은 왼쪽 서브트리이고, 오른쪽은 오른쪽 서브트리이다.

후위순회는 왼쪽, 오른쪽, 루트 순으로 출력하는 것이다. 그래서 전체 트리의 루트(root)를 기준으로 왼쪽 먼저 함수를 실행하고, 다음으로 오른쪽을 실행한다. 그리고 마지막에 root를 출력한다.


정답 코드

import sys
  
def dnc(preorder,inorder):
  if not preorder:
    return
  if len(preorder)==1:
    print(preorder[0], end=' ')
    return
  if len(preorder)==2:
    print(preorder[1],preorder[0], end=' ')
    return

  root = preorder[0] #전위순회의 첫번째 오는 수는 전체 트리의 루트
  root_index = inorder.index(root)

  left_pre = preorder[1:root_index+1]
  left_in = inorder[:root_index]
  dnc(left_pre,left_in)

  right_pre = preorder[root_index+1:]
  right_in = inorder[root_index+1:]
  dnc(right_pre,right_in)

  print(preorder[0], end=' ')

T = int(sys.stdin.readline())
for i in range(T):
  N = int(sys.stdin.readline())
  preorder = list(map(int, sys.stdin.readline().split()))
  inorder = list(map(int, sys.stdin.readline().split()))
  dnc(preorder,inorder)
  print()