[트리] 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
아이디어
- 문제에 나온 postorder 의사코드를 활용
- 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()
Author And Source
이 문제에 관하여([트리] 1068, 4256), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@isg/트리-1068-4256저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)