[SWEA #1231, Python ] 중위순회

[풀이]

🐤 내 원래 풀이

def in_order(n):
    global result
    if n > 0: #돌아오는 조건
        in_order(left[n])
        result += word[n]
        in_order(right[n])

for tc in range(1,11):
    result = ""
    V = int(input())
    left = [0]*(V+1)
    right = [0] *(V+1)
    parent = [0] *(V+1)
    word = [0] *(V+1)
    for _ in range(V):
        tmp = list(map(str,input().split()))
        word[int(tmp[0])] = tmp[1] #단어 저장하기
        if len(tmp) == 3:
            left[int(tmp[0])] = int(tmp[2])
            parent[int(tmp[2])] = int(tmp[0])
        elif len(tmp) == 4:
            left[int(tmp[0])] = int(tmp[2])
            parent[int(tmp[2])] = int(tmp[0])
            right[int(tmp[0])] = int(tmp[3])
            parent[int(tmp[3])] = int(tmp[0])
    in_order(1)
    print(f'#{tc} {result}')

나는 left, right를 만들어서 각각의 값들을 저장해주고, 그다음 중위순회로 조회하였다. 그런데 다른분들 풀이를 보니까 내 코드 길이의 1/2인거 아닌가...! 이게 머선 129,, 해서 확인해봤는데 이건 완전이진트리의 특성을 사용하면 짧게 풀 수 있는 것이였다!!!

🐔 완전 이진트리라는 정의 활용

완전 이진트리는 노드가 n개있으면, 비어있지 않고 1~n 자리에 모두 노드가 존재하는 것! 그렇다 보니까 자연스럽게 부모의 왼쪽 subtree의 node는 부모 node가 n번이라고 할때, 왼쪽 n*2, 오른쪽 2*n+1 임을 활용해서 코드를 확 줄일 수 있다. 따로 저장하지 않고, slicing으로 그 node에 저장되는 값만을 저장하고 => 순회하면 되는것!

def in_order(n):
    global result
    if 0<n<=V:
        if visit[n] == False:
            in_order(n*2)
            visit[n] = True
            result += tree[n]
            in_order(n*2+1)

#완전 이진트리이면 이방법가능!!!! => 그리고 값이 주어져도 문제 x
for tc in range(1,11):
    V = int(input())
    result = ""
    tree = [0]#반드시 하나가 들어있어야 에러 발생 x
    visit=[False]*(V+1)
    for _ in range(V):
        tree.append(input().split()[1]) #해당 정점의 저장되는 값만 tree에 저장하기
    in_order(1)
    print(f'#{tc} {result}')