ch14-1(leetcode 104). 이진 트리의 최대 깊이

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 104번 ( https://leetcode.com/problems/maximum-depth-of-binary-tree/ )

 

✅교재를 참고하지 않은 풀이: 재귀

 

input으로는 TreeNode 타입의 root 노드 하나가 주어지고, 이를 통해 트리 전체의 깊이를 알아내는 문제이다. 

root 노드부터 아래로 내려가면서 트리 전체를 탐색해야 하므로 재귀 함수로 구현할 수 있다. 

 

탐색하는 노드의 값이 없거나, 탐색하는 노드의 left, right child 노드가 모두 없다면 탐색을 중단하고 현재까지 탐색한 깊이 값을 리턴한다.

탐색하는 노드의 값이 있다면 현재 깊이에 1을 더해준다. 

 

특정 노드의 높이는 현재 노드에서부터 leaf 노드에 도달하는 데 필요한 레벨(경로) 개수이다. 이때 left subtree와 right subtree의 leaf까지의 경로 수가 다를 수 있는데 이 경우 더 긴 쪽을 골라야 한다. 

 

class Solution(object):

    def maxDepth(self, root):

        if root is None:
            return 0
        
        def traverse(node, count):
            if node is None:
                return count

            if node.left is None and node.right is None:
                return count
            
            return max(traverse(node.left, count+1), traverse(node.right, count+1))

        return traverse(root, 1)

 

✅교재를 참고하지 않은 풀이: BFS

트리의 레벨을 탐색하는 경우 BFS로도 풀 수 있다. 

DFS는 스택으로 구현하며 LIFO 구조이고, BFS는 큐로 구현하므로 FIFO 구조이다. 

root 노드에서 시작해서 가장 위의 노드들부터 큐에 넣을 것이고, FIFO 구조이므로 그 노드들이 먼저 나올 것이다. 

 

참고로 파이썬에서 큐를 구현할 때는 데크(deque) 자료형을 사용하는 것이 일반적이다. 파이썬이 아닌 C언어로 구현된 모듈이기도 하고, 정확히는 큐가 아닌 데크이기 때문에 맨 앞과 맨 뒤에서 원소를 제거, 추가하는 것이 모두 가능하기 때문이다. 

 

맨 처음 root 노드를 큐에 넣은 상태가 시작 상태이다. 

deque = collections.deque([root])

 

BFS는 재귀함수로 구현할 수 없으므로 반복문을 사용한다. while문으로 큐가 빌 때까지 실행한다. 

먼저 큐의 맨 앞에서 원소를 하나 뺀다. 맨 처음은 root 노드가 될 것이다. 

그리고 이 노드의 left, right child가 있는지를 각각 확인하고 있다면 큐의 맨 뒤에 추가한다. 

current = queue.popleft()

if current.left:
    queue.append(current.left)
if current.right:
    queue.append(current.right)

 

주의할 점은 현재 큐에 있는 모든 노드를 대상으로 해당 노드들의 left, right child를 추가해야 한다. 그래야 큐에 레벨 순서대로 노드들이 들어올 수 있다. 

즉 while문이 한 번 실행될 때마다 이전 레벨의 노드를 큐의 앞쪽에서부터 전부 제거하고, 그 다음 레벨의 노드를 큐의 맨 뒤에 추가한다고 볼 수 있다. 현재 큐에 있는 모든 노드들에 대해서 위의 로직을 적용하려면, while문 내부에 별도의 for loop를 선언해서 큐의 길이만큼 반복해 주면 된다.