1991 트리 순회

드디어 마주한 거대한 장벽.. 그래프..

아이디어 (풀이법)

요구사항을 그대로 구현만 하면 된다.

입력받기 (전처리)

각 노드 - 왼쪽 자식 노드 - 오른쪽 자식 노드 순서이므로,

n = int(input())

tree = {}
preorder_stack = []
inorder_stack = []
postorder_stack = []

for _ in range(n):
    parent, left, right = input().split()
    visited = False
    tree[parent] = [left, right, visited]

트리는 일단 딕셔너리로 구현. (해당 노드 - 자식 노드 관계로 주어져서 직관적으로 딕셔너리로 해야겠다는 생각이 들었다)
스택은 하다 보니까 필요할 것 같아서 추가.

구현

전위 / 중위 / 후위 각각

# 트리 방문 초기화
def tree_clear(tree):
    for node in tree.keys():
        tree[node][2] = False


# 전위 순회
def preorder(tree, node):
    if not tree[node][2]:
        tree[node][2] = True
        preorder_stack.append(node)

    if tree[node][0] != ".":
        preorder(tree, tree[node][0])

    if tree[node][1] != ".":
        preorder(tree, tree[node][1])


# 중위 순회
def inorder(tree, node):
    if tree[node][0] != ".":
        inorder(tree, tree[node][0])

    if not tree[node][2]:
        tree[node][2] = True
        inorder_stack.append(node)

    if tree[node][1] != ".":
        inorder(tree, tree[node][1])


# 후위 순회
def postorder(tree, node):
    if tree[node][0] != ".":
        postorder(tree, tree[node][0])

    if tree[node][1] != ".":
        postorder(tree, tree[node][1])

    if not tree[node][2]:
        tree[node][2] = True
        postorder_stack.append(node)


# 출력
preorder(tree, "A")
print("".join(preorder_stack))
tree_clear(tree)
inorder(tree, "A")
print("".join(inorder_stack))
tree_clear(tree)
postorder(tree, "A")
print("".join(postorder_stack))

풀어놓고 나중에 확인해보니 - 스택을 이용한 재귀 -> 이건 DFS다
라는 것을 알수있었다. (전위/중위/후위는 함수 내에서 순서만 달랐음)