Baekjoon 1991번 트리 순회

💭 문제가 궁금하다면?

내가 시도한 방법

• 아스키코드 함수 ord()와 chr()을 활용
  • 알파벳으로 들어오는 노드 정보를 배열에 담기 위해
  • 노드 이름으로 출력하기 위해
• 자식 노드가 없는 경우 -1로 기본값 설정
  • 0 <= 알파벳 < 26이기 때문에 유효한 노드인지 판별하기 위해

def preorder(v):
    if v >= 0:
        print(chr(v + ord('A')), end='')
        preorder(tree[v][0])
        preorder(tree[v][1])


def inorder(v):
    if v >= 0:
        inorder(tree[v][0])
        print(chr(v + ord('A')), end='')
        inorder(tree[v][1])


def postorder(v):
    if v >= 0:
        postorder(tree[v][0])
        postorder(tree[v][1])
        print(chr(v + ord('A')), end='')


N = int(input())

tree = [[] for _ in range(N)]

for _ in range(N):
    parent, *children = map(lambda x: ord(x) - ord('A') if x !='.' else -1, input().split())
    tree[parent].extend(children)


preorder(0)
print()
inorder(0)
print()
postorder(0)

배운 점

이진 트리(binary tree)

• 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조

이진 탐색 방법

• 전위 순회 : 부모 - 왼쪽 자식 - 오른쪽 자식

• 중위 순회 : 왼쪽 자식 - 부모 - 오른쪽 자식

• 후위 순회 : 왼쪽 자식- 오른쪽 자식 - 부모

느낀 점

• 오랜만에 트리 문제를 푸니까 습관처럼 완전이진트리라고 착각도 하고 중위 순회 특징도 잊고... 자식 노드 순회할 때 for를 사용했었다... 잊지말자 전위, 중위, 후위...
• 요즘 filter와 map, lambda 그리고 *까지 활용해서 입력 받을 때 최대한 불필요한 작업이 반복되지 않게 신경쓰고 있는데 다시 연습할 수 있는 문제를 만나 좋았다. 물론 위의 코드에는 filter가 없다.. 중간에 설계를 잘못해서 지웠다...설계를 대충하고 문제를 풀었더니...싹 뒤집어 엎었다(완전이진트리라고 착각해서...ㅎㅎ) 역시 무엇보다도 설계, 설계가 참 중요한 거 같다.
• 저번 아스키코드를 활용한 문제에서는 ord('a') - 65이런 식으로 코드를 짰는데, 가독성을 고려했을 때 ord('a') - ord('A')가 더 좋을 거 같다는 피드백을 받았다!! 바로 적용해볼 수 있는 기회가 주어져서 좋았닿ㅎㅎ