22856 트리 순회 python 풀이

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

22856번: 트리 순회

 

이 문제 풀다가 잘 안되서 리마인드용으로 1991 번도 다시 봤다 

1991번 풀이 

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

1991번: 트리 순회

n = int(input())
tree = {}
for i in range(n):
    a, b, c = input().split()
    tree[a] = [b, c]

def preorder(root):
    if root != '.':
        left, right = tree[root]
        print(root, end='')
        preorder(left)
        preorder(right)

def inorder(root):
    if root != '.':
        left, right = tree[root]
        inorder(left)
        print(root, end='')
        inorder(right)

def postorder(root):
    if root != '.':
        left, right = tree[root]
        postorder(left)
        postorder(right)
        print(root, end='')

preorder('A')
print()
inorder('A')
print()
postorder('A')

왼쪽 자식 노드 -> 루트 노드 -> 오른쪽 자식 노드 방문하는게 중위 순회이다. 

백준 22856번 트리순회 문제에서는 결국 노드를 방문하는 순서는 동일하다. 따라서 중위순회와 유사 중위 순회 둘다 마지막으로 방문하는 노드는 동일하다. 

이를 이용하여 유사 중위 순회에서 재귀 함수의 호출을 맨 마지막 중위 순회 노드가 나왔을 때 탈출하도록 코드를 짰다. 

왼쪽 자식 노드와 오른쪽 자식 노드가 존재하지 않았을 때 다시 root 노드로 올라가는 경로까지 count 해주어야 한다는 것이다. 

그리고 파란 선으로 표시한 root노드에서 마지막 노드까지의 거리를 세어주고 count 수에서 dist를 빼준다. 

# root 에서 맨 마지막 노드 거리
while True:
    if tree[r][1] != -1:
        dist += 1
        r = tree[r][1]
    else:
        break

similar_inorder(1)
print(count-dist)

 

전체 코드 (pypy로 통과함)

import sys
sys.setrecursionlimit(10**6)
n = int(input())
tree = {}
answer = 0
for _ in range(n):
    a, b, c = map(int, input().split())
    tree[a] = [b, c] # left node, right node

path = []
def inorder(root):
    global path
    if root != -1:
        inorder(tree[root][0])
        path.append(root)
        inorder(tree[root][1])
inorder(1)
count = 0
def similar_inorder(root): # root node 는 항상 1번
    global count
    # 왼쪽, 오른쪽이 -1 일때 root 로 back 해야 함
    if tree[root][0] != -1:
        similar_inorder(tree[root][0])
        count += 1
    if path[-1] == root:
        return
    count += 1 # root 방문
    if tree[root][1] != -1:
        similar_inorder(tree[root][1])
        count += 1

dist = 0
r = 1
# root 에서 맨 마지막 노드 거리
while True:
    if tree[r][1] != -1:
        dist += 1
        r = tree[r][1]
    else:
        break

similar_inorder(1)
print(count-dist)