★Tree Upper-Intermediate I - 3 Solved★

★ 1991 트리 순회 ★

 

import sys
input=sys.stdin.readline

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

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

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

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

pre_order('A')
print()
in_order('A')
print()
post_order('A')
print()

 

🌳 전형적인 트리 순회 문제. 트리를 딕셔너리로 생성하고 각 노드의 left / right를 tuple 형태로 노드의 value로 저장

---

★ 9934 완전 이진 트리 ★

 

import sys
input=sys.stdin.readline

def in_order(tree,start):
    if (start[0]+1)<K and tree[start[0]+1][start[1]*2] == 0:
        in_order(tree,(start[0]+1,start[1]*2))
    if tree[start[0]][start[1]] == 0:
        tree[start[0]][start[1]] = ns[0]
        del ns[0]
    if (start[0]+1)<K and tree[start[0]+1][start[1]*2+1] == 0:
        in_order(tree,(start[0]+1,start[1]*2+1))

K=int(input())
tree,ns=[],list(map(int,input().split()))
for j in range(0,K):
    level=[0]*(2**j)
    tree.append(level)
in_order(tree,(0,0))

for level in tree:
    print(*level)

 

🌳 왼쪽 - 루트 - 오른쪽 순서인 in-order tree traversal 유형

 

🌳 

① 완전이진트리이므로 K가 주어지면 이에 맞게 level 별 모든 node를 2차원 list로 구현(0 초기화)

② in-order traversal 구현(root node (0,0) 부터 시작)

③ 왼쪽부터 root 그리고 오른쪽 traversal(좌표는 아래 그림과 같이 진행) (이 때, 다음 level 진행 시 list index 범위 조건 추가)

④ 값이 0이라면 아직 traversal 안했으므로 recusrion 시작

⑤ left 진행 후 root일 때 해당 tree의 index에 값 배치. ns 맨 앞의 값을 차례대로 배치하면 되므로 배치하고 맨 앞 원소 삭제

⑥ 모든 traversal 완료하면 0으로만 이루어진 tree가 값의 배치 후 tree 완성

---

★ 11725 트리의 부모 찾기 ★

 

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

n=int(input())
graph=[[] for _ in range(n+1)]
parent=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(start):
    for v in graph[start]:
        if parent[v] == 0:
            parent[v] = start
            dfs(v)

dfs(1)

for x in range(2,n+1):
    print(parent[x])

 

🌳 시작 지점 1부터 시작해서 DFS 형식으로 parent[]의 값이 0이라면 해당 위의 부모 노드 값을 parent[]에 넣어주기 (DFS 변형)

🌳 즉, 트리의 부모노드를 DFS로 서칭하면서 parent라는 list에 계속 update하며 풀 수 있다.(BFS도 물론 가능)

: 즉, 노드를 방문하면서 visited를 True로 하지 않고 visited에 부모노드번호를 넣는다는 점만 다름

---