[알고리즘 문제풀이] 트리의 높이와 너비

문제 제목 : 트리의 높이와 너비

문제 난이도 : 중

문제 유형 : 트리, 구현

https://www.acmicpc.net/problem/2250
시간 제한 : 2초
메모리 제한 : 128MB

문제풀이 아이디어

1. 중위 순회 이용 -> 왼쪽 노드부터 방문할 수 있다.
2. 추가적으로 높이에 대한 값인 level 값을 저장
   -> 동일한 level에 x축 값을 이용하여 너비 계산

< 소스코드 >

class Node:
    def __init__(self, number, left_node, right_node):
        # node 1번이 항상 루트노드 x -> 루트노드가 있는지 확인 필요
        self.parent = -1
        self.number = number
        self.left_node = left_node
        self.right_node = right_node

# 중위 순회 진행
def in_order(node, level):
    global level_depth, x
    level_depth = max(level_depth, level)
    # 왼쪽 노드 방문
    if node.left_node != -1:
        in_order(tree[node.left_node], level + 1)
        
    level_min[level] = min(level_min[level], x)
    level_max[level] = max(level_max[level], x)
    x += 1
    # 오른쪽 노드 방문
    if node.right_node != -1:
     in_order(tree[node.right_node], level + 1)
     
n = int(input())
tree = {}
level_min = [n]
level_max = [0]
root = -1
x = 1
level_depth = 1

# tree 초기화
for i in range(1, n + 1):
    tree[i] = Node(i, -1, -1)
    level_min.append(n)
    level_max.append(0)

for _ in range(n):
    number, left_node, right_node = map(int, input().split())
    tree[number].left_node = left_node
    tree[number].right_node = right_node
    # 부모노드를 찾을 수 있도록
    if left_node != -1:
     tree[left_node].parent = number
    if right_node != -1:
     tree[right_node].parent = number

for i in range(1, n + 1):
    if tree[i].parent == -1:
     root = i

in_order(tree[root], 1)

result_level = 1
result_width = level_max[1] - level_min[1] + 1

for i in range(2, level_depth + 1):
    width = level_max[i] - level_min[i] + 1
    if result_width < width:
        result_level = i
        result_width = width

print(result_level, result_width)