SWEA 5174 subtree (파이썬)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

---

아이디어

1. 간단하다. 트리의 간선 정보가 있고, 이를 이용해서 트리의 왼쪽, 오른쪽 자식을 넣어주고
2. 전위든 중위든 후위든 탐색하여 1씩 더하면 된다.

 

---

풀이

cnt = 0
def inorder(v):
    global cnt
    if v == 0:
        return
    inorder(L[v])
    cnt += 1
    inorder(R[v])
    return cnt

for tc in range(int(input())):
    E, N = map(int, input().split())
    arr = list(map(int, input().split()))
    tree = [0] * (E + 2)
    L = [0] * (E + 2)
    R = [0] * (E + 2)
    P = set()

    for i in range(0, E * 2, 2):
        parent, child = arr[i], arr[i + 1]
        if L[parent] == 0:
            L[parent] = child
        else:
            R[parent] = child
        P.add(child)

    print(f'#{tc+1} {inorder(N)}')
    cnt = 0