백준 1991번 : 트리 순회 (Python) (비재귀 반복문)

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

n = int(input())
graph = dict()
for _ in range(n) :
    node, left, right = input().split()
    graph[node] = [left, right]
    
def preorder_stack(node) :
    answer = list()
    stack = [node]
    while stack :
        node = stack.pop()
        # 루트 노드 방문
        answer.append(node)
        # 오른쪽 자식 노드 있으면 스택에 삽입
        if graph[node][1] != "." :
            stack.append(graph[node][1])
        # 왼쪽 자식 노드 있으면 스택에 삽입
        if graph[node][0] != "." :
            stack.append(graph[node][0])
    return answer          
    
def inorder_stack(node) :
    answer = list()
    stack = list()
    while node != "." or stack :
        # 현 노드가 존재하면 = 왼쪽 서브트리를 더 돌 수 있으면
        if node != "." :
            # 스택에 현 노드 삽입
            stack.append(node)
            # 현 노드를 왼쪽 자식 노드로 변경
            node = graph[node][0]
        # 현 노드가 존재하지 않으면 = 왼쪽 서브트리를 다 돌았으면
        else :
            # 현 노드(.)의 루트 노드(= 왼쪽 서브트리의 마지막 노드) 방문
            node = stack.pop()
            answer.append(node)
            # 현 노드를 루트 노드의 오른쪽 자식 노드로 변경
            node = graph[node][1]
    return answer
    
def postorder_stack(node) :
    answer = list()
    stack = [node]
    # 실제 순서 역순으로 방문하므로 방문 순서 저장
    order = list()
    while stack :
        node = stack.pop()
        # 가장 마지막에 방문할 루트 노드 먼저 order에 삽입
        order.append(node)
        # 왼쪽 자식 노드 있으면 스택에 삽입
        if graph[node][0] != "." :
            stack.append(graph[node][0])
        # 오른쪽 자식 노드 있으면 스택에 삽입
        if graph[node][1] != "." :
            stack.append(graph[node][1])
    # order 역순으로 반환
    while order :
        node = order.pop()
        answer.append(node)
    return answer

print("".join(preorder_stack("A")))
print("".join(inorder_stack("A")))
print("".join(postorder_stack("A")))

여러모로 재귀로 구현하는 것이 훨씬 코드가 간결하다.

아래는 재귀로 구현한 코드.

n = int(input())
graph = dict()
for _ in range(n) :
    node, left, right = input().split()
    graph[node] = [left, right]
    
pre_answer = list()
def preorder(node) :
    if node == "." :
        return
    pre_answer.append(node)
    preorder(graph[node][0])
    preorder(graph[node][1])
    
in_answer = list()
def inorder(node) :
    if node == "." :
        return
    inorder(graph[node][0])
    in_answer.append(node)
    inorder(graph[node][1])
    
post_answer = list()
def postorder(node) :
    if node == "." :
        return
    postorder(graph[node][0])
    postorder(graph[node][1])
    post_answer.append(node)
    
preorder("A")
inorder("A")
postorder("A")
print("".join(pre_answer))
print("".join(in_answer))
print("".join(post_answer))