[트리] 1068, 4256

1. 1068-트리

링크 - https://www.acmicpc.net/problem/1068

코드

import sys
input = sys.stdin.readline
INF = int(1e9)

def dfs(k,n):
    if k>=n:
        return 
    for i in range(n):
        if tree[i]==k:
            tree[i]=INF
            dfs(i,n)
    return


n = int(input())
tree = list(map(int,input().split()))

k = int(input()) #삭제할 노드

tree[k] = INF

dfs(k,n)
count=0

#리프노드 개수 구하기
for i in range(n):
    if tree.count(i)==0 and tree[i]!=INF:
        count+=1
print(count)

크게 2가지 부분으로 구분할 수 있다.

DFS 부분

DFS를 통해서 노드를 제거해준다. (INF값을 넣어 제거표시를 함)

k는 부모노드, n은 입력받은 노드를 의미한다.
재귀적으로 탐색하며 삭제한 노드를 부모노드로 가지는 노드들을 삭제한다.

리프노드 탐색부분

배열을 전체 탐색하면서 자신을 부모노드로 가지는 노드가 없고 값이 INF가 아니라면 count값을 증가시킨다.

2. 4256-트리

링크 - https://www.acmicpc.net/problem/4256

아이디어

1. 문제에 나온 postorder 의사코드를 활용
2. preorder와 inorder를 통해서 left subtree와 right subtree를 나눈다.

문제에 나온 예시)

preorder- [3,6,5,4,8,7,1,2]
inorder- [5,6,8,4,3,1,2,7]

preorder의 경우 루트노드가 맨 처음 출력이 된다.

inorder을 보면 3을 기준으로 왼쪽은 실제 트리에서 왼쪽 서브트리이고, 오른쪽은 루트노드의 오른쪽 서브트리이다.

이를 이용하여 재귀적으로 문제를 푼다.

코드

import sys
input = sys.stdin.readline

def toPostorder(preorder,inorder):
    if len(preorder)==1:
        print(preorder[0],end=" ")
        return
    elif len(preorder)==2:
        print(preorder[1],preorder[0],end=" ")
        return
        
    middle = preorder[0]
    middle_idx = inorder.index(middle)
    
    left_in = inorder[:middle_idx]
    left_pre = preorder[1:middle_idx+1]
    if len(left_in)!=0:
        toPostorder(left_pre,left_in)
    
    right_in = inorder[middle_idx+1:]
    right_pre = preorder[middle_idx+1:]
    if len(right_in)!=0:
        toPostorder(right_pre,right_in)
    
    print(middle,end=" ")

t = int(input())

for _ in range(t):
    n = int(input())
    preorder = list(map(int,input().split()))
    inorder = list(map(int,input().split()))
    
    toPostorder(preorder,inorder)
    print()