(Python/🥈2)백준 알고리즘 1991번: 트리순회

 

문제 바로가기 

트리 순회

문제:

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

입력:

 

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력:

 

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

풀이 :

재 어려운 재귀,, 재귀풀이에 자신감을 얻을때까지 재귀를 풀어볼 생각이다.

https://www.youtube.com/watch?v=uSSC0aKXbWQ 

이 문제를 보고 나도 생각을 좀 바꿔서 해야겠다고 생각했다. 평소 재귀문제를 풀때 재귀를 부르고 나서 상황도 이해하려고 했지만. 그것은 프로그래밍에게만 맡긴다라고 생각하고 풀어본다.

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(sys.stdin.readline())

tree = {}
for i in range(N):
    root, left, right = sys.stdin.readline().strip().split()
    tree[root] = [left,right]
def solution(root):
    if root != ".":
        print(root, end="")
        solution(tree[root][0])
        solution(tree[root][1])


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


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


solution("A")
print()
solution2("A")
print()
solution3("A")

 

그러면 이런식인데 하나를 보자면

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

 

Root가 . 이 아니면

1. 루트를 프린트하고

2. 왼쪽루트를 탐색하고

3. 오른쪽을 탐색한다 .

 

라고 이해 하면 될것 같다.