SWEA 1231. 중위순회(Python)(D4)

단순한 중위순회 문제이다.

중위순회란?

- 트리에서 왼쪽자손, 루트, 오른쪽 자손 순으로 방문
- 트리가 위와 같은 경우, A(T1)에서 시작해, 왼쪽자손(T1)로 넘어감
- T1에서 왼쪽자손인 D부터 방문, 이후 B, 이후 T3그룹을 방문.
- 결과적으로 D-B-H-E-I-A-F-C-G 순서대로 방문!

단순하게 노드와 노드의 왼쪽자손, 오른쪽자손이 주어지고, 노드의 값(문자)가 주어지므로
재귀함수로 중위순회 후 return 값들을 다 더해서 출력!

res=[]
def calc(x):
    if x:
        left_val=calc(left[x])
        right_val=calc(right[x])
        return str(left_val)+tree[x]+str(right_val)
    else:
        return ""

for m in range(10):
    tmp=""
    N=int(input())
    tree,left,right=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    for i in range(N):
        S=list(map(str,input().split()))
        tree[int(S[0])]=S[1]
        if len(S)>=3:
            left[int(S[0])]=int(S[2])
        if len(S)>=4:
            right[int(S[0])]=int(S[3])
    tmp=calc(1)
    res.append(tmp)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))