[백준 문제풀이] 2250번 : 트리의 높이와 너비

https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

 

💡중위순회를 통해 앞에서부터 차례대로 탐색

 

✔소스코드

N=int(input())
matrix=[[0]*2 for i in range(N+1)]
node = [0 for i in range(N + 1)]
row = [[] for i in range(N + 1)]

#입력받은 수를 matrix에 채우기
for i in range(N):
    ro,le,ri=map(int,input().split())
    matrix[ro][0]=le
    matrix[ro][1]=ri
    node[ro]+=1
    if le!=-1:
        node[le]+=1
    if ri!=-1:
        node[ri]+=1
#inorder를 위한 root노드 정하기
for i in range(1,N+1):
    if node[i]==1:
        root=i
        
num=1

def inorder(root, level):
    global num
    if matrix[root][0] != -1:
        inorder(matrix[root][0], level + 1)
    row[level].append(num)
    num += 1
    if matrix[root][1] != -1:
        inorder(matrix[root][1], level + 1)

inorder(root,1)

#너비 구하기
width=max(row[1])-min(row[1])+1
level=1
#처음부터 가장 넓은 레벨찾기
for i in range(2,N+1):
    if row[i]:
        if width < max(row[i]) - min(row[i]) + 1:
            width = max(row[i]) - min(row[i]) + 1
            level = i

print(level, width)