[알고리즘]백준22856 트리 순회 - 파이썬

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

22856번: 트리 순회

 

[풀이 코드]

import sys
from sys import stdin
sys.setrecursionlimit(10**8)
input = stdin.readline

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

def in_order(node):
    if node.left_node != '-1':
        in_order(tree[node.left_node])
    a_list.append(node.data)
    if node.right_node != '-1':
        in_order(tree[node.right_node])

def similar_in_order(node):
    global cnt

    if node.left_node != '-1':
        similar_in_order(tree[node.left_node])
        cnt += 1

    if node.data == a_list[-1]: # 중위순회의 마지막 값과 같다면 종료
        print(cnt)
        exit(0)
    cnt += 1

    if node.right_node != '-1':
        similar_in_order(tree[node.right_node])
        cnt += 1


n = int(input())
tree = {}
for i in range(n):
    data, left_node, right_node = input().split()
    tree[data] = Node(data, left_node, right_node)

a_list = []
cnt = 0
in_order(tree['1'])
similar_in_order(tree['1'])

• 이 문제를 풀기 전에 백준 1991 트리 순회를 풀었기 때문에 쉽게? 풀 수 있었다. 중위 순회에 대한 개념을 잘 이해하고 있다면 충분히 쉽게 풀 수 있었던 문제였던 것 같다.
• in_order함수는 중위순회로 나온 결과의 마지막 값을 저장하기 위함이다. similar_in_order함수의 종료 조건이 중위 순회로 나온 마지막 값과 같기 때문이다.

#예제 입력 케이스

2
1 2 -1
2 -1 -1

• 위 예제 입력 케이스를 넣어 값이 '2'가 나오는지 확인해보면 좋을 것 같다.