[BOJ] 1991 | 트리 순회

문제링크

---

1991 | 트리 순회

풀이과정

---

Softeer | 거리 합 구하기 문제를 풀다가 내가 트리를 이해를 잘 못하나 .. 라는 생각으로 백준 트리섹션으로 돌아왔다 2 .. 하아

트리의 순회 문제였고, 이진 트리를 만들 수 있는지를 보는 문제같았다.

이진트리는 각각의 노드가 최대 2개의 자식 노드를 가지는 트리를 말한다 ! 그래서 무조건 [left, right] 를 가지게 하면 된다.

루트 노드는 무조건 A라서 여기서부터 순회를 어떻게 할건지 봐주면 된다. 문제에서 친절하게 설명해주셨다.

1. 전위 순회(preorder traversal)
   루트 -> 왼쪽 자식 -> 오른쪽 자식 순서

2. 중위 순회(inorder traversal)
   왼쪽 자식 -> 루트 -> 오른쪽 자식 순서

3. 후위 순회(postorder traversal)
   왼쪽 자식 -> 오른쪽 자식 -> 루트 순서
   
   
   
   

코드

---

import sys
N = int(input())

tree = {}
for _ in range(N):
    item, left, right = sys.stdin.readline().split()
    tree[item] = [left, right]

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

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

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

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

결과

---