출처 https://www.acmicpc.net/problem/9934

코드

import sys

input = sys.stdin.readline
K=int(input())
arr = [[]  for _ in range(K)   ]
inorder = list(map(int,input().split()))

def dfs(inorder,depth):
    mid = (len(inorder) // 2) 
    # 예제입력 1이 Test Case 라고 했을 때, inorder = [2,1,3] ==> mid = 1 ==> 1
    arr[depth].append(inorder[mid])

    #종료조건
    if len(inorder) == 1:
        return
    
    #재귀 시작
    dfs(inorder[:mid], depth+1) # 왼쪽 서브트리 순회
    #예제입력 1을 기준으로 --> 1이 mid이기 떄문에 2가 inorder 실행된다.[2] 들어감 
    #
    dfs(inorder[mid+1 :], depth+1) #오른쪽 서브트리 순회


dfs(inorder,0)

for i in arr:
    print(*i)

코드분석

• arr를 2차원 리스트로 선언한 이유는 Tree의 Depth를 나타내기 위해서다.

• inorder는 사용자로부터 입력받은 값을 저장하는 리스트로 중위순회 할 때 Focus

• KeyPoint 메소드는 dfs다. 파라미터 값으로 inorder, depth를 받고 있다.

mid = (len(inorder) // 2) 

1. 이 부분은 서브트리를 구하기 위해서 mid값을 구하는 것이다.
2. arr[depth].append(inorder[mid]) : arr의 깊이에 해당되는 
inorder(순회한 mid값을) arr에 저장한다.

• 예제 Test Case 1번을 실행하면

2 1 3
mid = 1 --> 재귀로 inorder[: mid] ,depth+1실행
이 부분 arr에 저장할 떄, 트리의 순서를 보게 되면 2[root], 1[left] 3[right] 인데 --> 1[왼쪽] 먼저 실행하고 -> 2[root] 실행하고 -> 3[right] 실행해서 --> 중위순회 구현