트리 깊이 구하는 방식

1. BFS 

def depth(tree,root):
    queue = deque()
    queue.append((root,1))
    visit = []
    count = 1
    while queue: #while문을 돌리는 만큼 깊이 증가 
        v, count= queue.popleft()
        visit.append(v)
        for node in tree[v]:
            if node != '.' and node not in visit:
                queue.append((node,count+1))
    
    return count 

각 노드에서의 count를 계속 늘려주고 while문을 빠져나왔을 때 마지막 count를 리턴하면 최대 깊이를 구할 수 있다. 

 

2. 재귀 

def depth(tree,root):
    if root =='.':
        return 0

    left = depth(tree,tree[root][0])
    right = depth(tree,tree[root][1])

    return max(left,right)+1

재귀를 통해 리프노드에서부터 위로 올라가면서 1씩 증가 시키는 방식이다.

루트까지 오면 최대 깊이를 구할 수 있다. 

재귀를 통해 다른 응용문제들도 쉽게 풀 수 있으므로 꼭 기억해놓아야 할 것 같다.