[백준] 1991번 트리 순회 ★

💡문제접근

• 트리에 대한 개념을 유튜브로 보고 이해한 다음 문제를 풀었다.

• Python으로 트리를 구현하는 방법 : 딕셔너리를 사용

①. root를 key로 두고 left, right를 value로 둔다.

>>> tree[root] = left, right
>>> tree["A"] = "B", "C"

• 위의 코드에서 A는 부모 노드를 의미하고 B는 왼쪽 자식 노드, C는 오른쪽 자식 노드를 의미한다.

• B를 인덱싱하는 방법 : tree["A"][0] / C를 인덱싱하는 방법 : tree["A"][1]

②. 전위/중위/후위 순회마다 재귀함수 코드의 순서 바꾸기(탐색 방향 바꾸기)

# 한번 재귀할 때마다 탐색을 한번 더 하는 의미로 받아들이자
# 함수 안의 ~~order(tree[root][0]) 재귀함수는 왼쪽으로 끝까지 탐색한다는 의미
# 함수 안의 ~~order(tree[root][1]) 재귀함수는 오른쪽으로 끝까지 탐색한다는 의미
# root -> 출력하면 됨


# 1. 전위 순회 : 루트 -> 왼쪽 자식 -> 오른쪽 자식이므로 재귀함수 순서도 root출력문 -> 왼쪽 재귀함수 -> 오른쪽 재귀함수

def preorder(root): # 루트 -> 왼쪽 자식 -> 오른쪽 자식 순으로 탐색
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left -> left가 새로운 root가 된다.
        preorder(tree[root][1])  # right -> right가 새로운 root가 된다.
        

# 2. 중위 순회 : 왼쪽 자식 -> 루트 -> 오른쪽 자식이므로 재귀함수 순서도 왼쪽 재귀함수 -> root 출력문 -> 오른쪽 재귀함수
 
def inorder(root): # 왼쪽 자식 -> 루트 -> 오른쪽 자식 순으로 탐색
    if root != '.': 
    # TEST CASE를 예로 들면 B에서 tree[root][0] = "D"이고 D의 tree(root[0]) = "."이 돼서 root인 D를 출력하고 right로 넘어간다.
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right


# 3. 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 루트이므로 재귀함수 순서도 왼쪽 재귀함수 -> 오른쪽 재귀함수 -> root 출력문

def postorder(root): # 왼쪽 자식 -> 오른쪽 자식 -> 루트 순으로 탐색
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root

💡코드(메모리 : 31256KB, 시간 : 40ms)

import sys
input = sys.stdin.readline

N = int(input().strip())
tree = {}
for _ in range(N):
    root, left, right = map(str, input().strip().split())
    tree[root] = 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")

💡소요시간 : 40m(개념 포함)