[Algorithm] Tree

[thals0]

[BOJ] 1991. 트리 순회

• 전위 순회 (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회 (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회 (왼쪽 자식) (오른쪽 자식) (루트)

n = int(input())
tree = {}
for _ in range(n):
  root, left, right = input().split()
  tree[root] = [left, right]

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

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

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

preorder('A')
print()
inorder('A')
print()
postorder('A')

[thals0]

[BOJ] 트리의 순회 (복습 필요 🥊)

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))

nodeNum = [0] * (n + 1)
for i in range(n):
    nodeNum[inorder[i]] = i

def getPreorder(inStart, inEnd, postStart, postEnd):
    if (inStart > inEnd) or (postStart > postEnd):
        return

    root = postorder[postEnd]

    leftNode = nodeNum[root] - inStart
    rightNode = inEnd - nodeNum[root]

    print(root, end = " ")
    getPreorder(inStart, inStart + leftNode - 1, postStart, postStart + leftNode - 1)
    getPreorder(inEnd - rightNode + 1, inEnd, postEnd - rightNode, postEnd - 1)

getPreorder(0, n-1, 0, n-1)

[thals0]

[BOJ] 9934. 완전 이진 트리

from collections import defaultdict

k = int(input())
inorder = list(map(int, input().split()))
tree = defaultdict(list)
i = 0

def getTree(i, inorder):
  n = len(inorder)
  if n > 1:
    root = inorder[n//2]
    tree[i].append(root)
    i += 1
    getTree(i, inorder[:n//2])
    getTree(i, inorder[n//2+1:])
  elif n == 1:
    tree[i].append(inorder[0])

getTree(i, inorder)

tree = list(tree.values())
for i in range(k):
  print(*tree[i])

• defaultdict(list)를 사용하면 dictionary의 기본 형태를 List로해서 value값에 여러개 append가 가능해짐

• 예) 1 6 4 3 5 2 7 이면

  • 트리 딕셔너리 : defaultdict(<class 'list'>, {0: [3], 1: [6, 2], 2: [1, 4, 5, 7]})

• list에서 [] 빼고 print하는 방법 print(*list) 하면 된다.