[BOJ, Python] 1991 - 트리 순회 ( with Recursion )

1991번: 트리 순회

이진트리에서 순회하는 종류는 세 가지가 있다.

 

루트 노드를 기준으로 루트 노드 - 왼쪽 자식 트리 - 오른쪽 자식 트리를 순차적으로 방문하는 전위 순회,

왼쪽 자식 트리 - 루트 노드 - 오른쪽 자식 트리를 순차적으로 방문하는 중위 순회,

그리고 마지막으로 왼쪽 자식 트리 - 오른쪽 자식 트리 - 루트 노드를 방문하는 후위 순회다.

 

재귀함수 심화 대표 문제인 하노이탑 이동 순서처럼, 방문하는 순서에 맞게 재귀를 돌려주고 그 안에서 루트 노드를 로그 프린팅 하며 원하는 답을 출력할 수 있다.

nodes = dict()
for _ in range(int(input())):
    root, left, right = map(str, input().split())
    nodes[root] = [left, right]

# 전위 순회
def printPreorder(root):
	
    # 루트
    print(root, end= "")
    if nodes[root] == ['.', '.']:
        return
    
    # 왼쪽
    if nodes[root][0] != '.':
        printPreorder(nodes[root][0])
    
    # 오른쪽
    if nodes[root][1] != '.':
        printPreorder(nodes[root][1])

# 중위 순회
def printInorder(root):
	
    # 왼쪽
    if nodes[root][0] != '.':
        printInorder(nodes[root][0])
    
    # 루트
    print(root, end= "")
    if nodes[root] == ['.', '.']:
        return
    
    # 오른쪽
    if nodes[root][1] != '.':
        printInorder(nodes[root][1])

# 후위 순회
def printPostorder(root):

	# 왼쪽
    if nodes[root][0] != '.':
        printPostorder(nodes[root][0])
    
    # 오른쪽
    if nodes[root][1] != '.':
        printPostorder(nodes[root][1])
    
    # 루트
    print(root, end="")
    if nodes[root] == ['.', '.']:
        return

printPreorder('A')
printInorder('A')
printPostorder('A')