문제

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

Point

root 구하기

• 루트 노드가 1이 아닐 수도 있다.
• 루트노드는 자식노드일 수 없으므로, 자식 노드 정보를 입력 받을 때 자식노드로 들어온적 없는 노드가 루트노드다.
  

중위순회

• 중위순회로 이진트리를 순회하였다.
  -> 가장 왼쪽 열부터 차례로 순회
• depth도 파라미터로 넘겨주어서 tree에 노드번호와 함께 저장했다.
• 자식 depth = 부모 depth + 1
  

• 순회 후 tree )
  • 가장 왼쪽 열 노드부터 차례로 저장된다.
  • ( 노드번호, depth )
    

전체 코드

import sys
sys.setrecursionlimit(10**8)

n = int(input())

child = [[] for _ in range(n+1)]
root = set([x for x in range(1, n+1)])
for _ in range(n):
  p, a, b = [int(x) for x in input().split()]
  child[p].append(a)
  child[p].append(b)
  if a != -1:
    root.remove(a)
  if b != -1:
    root.remove(b)

tree = [0]
def inorder(x, depth) :
    global tree, n
    if x >= 1: # -1 : leaf노드 순회 중지
        inorder(child[x][0], depth+1) #왼쪽 자식 노드 호출
        tree.append((x, depth))
        inorder(child[x][1], depth+1) #오른쪽 자식 노드 호출

inorder(list(root)[0], 1)
      
row = [set() for _ in range(n+1)]
max_row = 1
for i in range(1,n+1):
  num, d = tree[i]
  row[d].add(i)
  max_row = max(max_row, d)

max_width = 1
asw_row = max_row

for i in range(max_row, 0, -1):
  width = max(row[i]) - min(row[i]) + 1
  max_width = max(max_width, width)
  if max_width == width:
    asw_row = i

print(f"{asw_row} {max_width}")