백준 22856. 트리 순회 - 파이썬

https://www.acmicpc.net/problem/22856

22856번: 트리 순회

• 중위순회를 하면서 거쳐갔던 노드들을 카운트하는 문제
• 재귀연산을 통해 전위, 중위, 후위 순회를 표현하는 법은 배웠지만, 그 순회를 이용해서 다른 문제를 푸는 문제는 처음이었더라 시간이 좀 걸렸던 문제

• 중위 순회에서 우리가 알 수 있는건, 트리의 가장 왼쪽 노드와 그 노드의 부모노드 그리고 리프노드 값이다!
• 유사 중위 순회에서 대부분의 값들은 다시 자기자신으로 돌아오지만, 리프노드를 호출한 함수는 돌아오지 않는다는 걸 체크

핵심코드

 

 

 

def inorder(t):
    global cnt, ans
    if t :
        left = inorder(c1[t])
        if left :
            cnt += 2
        if t == leaf_node :
            return -1
        right = inorder(c2[t])
        if right == -1 :
             cnt += 1
             return -1
        elif right :
            cnt += 2

        return t
    else :
        return 0