트리 순회

1991번: 트리 순회

주어진 트리를 전위순회, 중위순회, 후위순회를 하는 프로그램을 작성해야한다.

🚩내코드

n = int(input())
graph = []
for _ in range(n):
  graph.append(list(map(str, input().split())))
ans = [[], [], []]

def pre(node):
  for x in graph:
    if x[0] == node and x[1] == '.' and x[2] == '.':
      ans[0].append(node)
      return
    if x[0] == node:
      ans[0].append(node)
      pre(x[1])
      pre(x[2])

def inorder(node):
  for x in graph:
    if x[0] == node and x[1] == '.' and x[2] == '.':
      ans[1].append(node)
      return
    if x[0] == node and x[1] != '.':
      inorder(x[1])
      ans[1].append(node)
      inorder(x[2])
    if x[0] == node and x[1] == '.':
      ans[1].append(node)
      inorder(x[2])

def post(node):
  for x in graph:
    if x[0] == node and x[1] == '.' and x[2] == '.':
      ans[2].append(node)
      return
    if x[0] == node and x[1] != '.':  
      post(x[1])
      post(x[2])
      ans[2].append(node)
    if x[0] == node and x[1] == '.':
      post(x[2])
      ans[2].append(node)
      
pre('A')
inorder('A')
post('A')

for x in ans:
  print(''.join(x))

우선 통과는 했지만 풀이를 하면서 코드가 장황하고 지저분하다는 생각이 들었다.

🚩다른 정답자의 코드

import sys
 
N = int(sys.stdin.readline().strip())
tree = {}
 
for n in range(N):
    root, left, right = sys.stdin.readline().strip().split()
    tree[root] = [left, right]
 
 
def preorder(root):
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right
 
 
def inorder(root):
    if root != '.':
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right
 
 
def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root
 
 
preorder('A')
print()
inorder('A')
print()
postorder('A')

🚩아쉬웠던 점

• 중복되는 조건: x[0]가 node 인지 각 2번씩 확인한다. 노드로 탐색하는것이 아니라 인덱싱으로 탐색을 했다면 어떨까 하는 생각이 든다. 현재는 N개의 노드를 O(N)에 걸쳐서 탐색을 하니 O(N2)의 복잡도로 풀이를 하고 있다. 즉, N의 크기가 컸다면 시간초과가 나왔을 것 같다.
• 다른 정답자의 코드를 확인해보면 특별한 다른 조건없이 현재 탐색중인 루트 노드가 존재하는지만 확인한다. 저런 방식으로 접근을 했다면 좀더 간결하고 깔끔한 코드가 나올 수 있었을것 같다.