알고리즘

[LeetCode] 104. Maximum Depth of Binary Tree (Python)

이준언 2024. 10. 14. 16:38

안녕하세요

 

오늘은 리트코드 104번 Maximum Depth of Binary Tree 문제를 풀어보겠습니다.

 

 

이진 트리의 루트 배열이 주어졌을 때, 그것의 Maximum depth를 출력하는 함수를 정의하는 문제였습니다. 여기서 Maximum depth는 루트 노드에서 가장 멀리 있는 leaf 노드 까지의 거리입니다.

 

이 문제도 이전에 풀었던 94번 문제와 같이 두 가지 방법으로 풀 수 있습니다. BFS를 이용해서 푸는 방식, 재귀를 이용해서 푸는 방식이 있는데 차례대로 풀어보겠습니다. 

 

풀이 1. 

BFS를 구현하기 위해서는 queue 구조를 사용해야합니다. 큐에 각 레벨의 노드들을 추가하고 한 레벨씩 탐색이 끝날 때마다 깊이를 증가시킵니다. 큐가 비게 될 때가지 반복한 후 그동안 증가된 깊이가 트리의 최대 깊이가 됩니다.

 

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0 # 트리가 비어있으면 깊이는 0

        # 큐 구조를 사용한 BFS
        q = deque([root]) # 루트 노드를 큐에 넣고 시작
        depth = 0

        while q:
            depth += 1 # 한 레벨을 탐색할 때마다 깊이 증가
            level = len(q) # 현재 레벨에 있는 노드 개수

            for i in range(level): # 현재 레벨의 모든 노드를 큐에서 꺼내고, 자식 노드를 다시 큐에 넣음
                node = q.popleft() # 큐에서 노드를 하나 꺼냄
                if node.left:
                    q.append(node.left) # 왼쪽 자식이 있으면 큐에 넣음
                if node.right:
                    q.append(node.right) # 오른쪽 자식이 있으면 큐에 넣음

        return depth # 모든 레벨을 탐색한 후 깊이를 반환

 

풀이 2. 

재귀를 통해 푸는 방법 입니다. 기저 조건은 트리의 루트가 none이면 최대 깊이는 0이고, 현재 노드의 왼쪽과 오른쪽 자식 노드에 대해 각각 재귀호출을 진행하여, 두 서브트리 중 더 깊은 쪽에 1을 더해 호출합니다. 

 

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0 # 트리가 비어있으면 깊이는 0
            
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)


        return max(left_depth, right_depth) + 1

첫 번째 풀이 방식인 반복 방식은 큐를 사용해 트리의 각 레벨을 탐색하며 깊이를 계산하는 BFS 방식을 사용했습니다. 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n), 큐에 트리의 최대 너비만큼의 노드가 한 번에 들어가므로 공간 복잡도는 O(w) 입니다.

 

두 번째 풀이 방식인 재귀 방식은 DFS 방식을 사용했습니다. 각 노드를 방문할 때마다 재귀적으로 왼쪽과 오른쪽 자식 노드를 방문하였습니다. 마찬가지로 시간 복잡도는 O(n)이고, 공간 복잡도는 재귀 호출이 스택에 쌓이므로 트리 깊이 만큼의 공간이 필요하기 때문에 O(h)가 되겠습니다.

 

트리가 깊은 경우에는 BFS 방식이 재귀 호출로 인한 스택 오버플로우 문제를 피할 수 있어 좋고, 트리의 너비가 넓고 깊이가 얕은 경우, 재귀 방식 (DFS)이 더 간결하고 메모리 사용이 적어 효율적일 수 있습니다.

 

++ 개념 정리

1. BFS (Breadth-First Search, 너비 우선 탐색)

그래프나 트리에서 너비를 우선으로 탐색하는 방법. 

보통 큐(Queue) 자료 구조로 구현. 시작 노드를 큐에 넣고, 큐에서 노드를 꺼내면서 그 노드의 자식 노드들을 큐에 차례대로 넣는 방식으로 작동

 

2. DFS (Depth-First Search, 깊이 우선 탐색)

그래프나 트리에서 깊이를 우선으로 탐색하는 방법.

트리에서는 루트에서 시작해 왼쪽 또는 오른쪽으로 끝까지 내려간 후 다시 위로 돌아가서 다른 방향으로 내려가며 탐색

주로 재귀를 통해 구현. 현재 노드를 방문한 후, 왼쪽 또는 오른쪽 자식을 재귀적으로 호출하여 내려감. 

 

3. 큐 (Queue)

큐는 FIFO(First in, First Out) 구조를 가지는 자료구조. 선입선출. 먼저 들어간 데이터가 먼저 나옴. 

enqueue: 데이터를 큐의 끝에 추가

dequeue: 큐의 앞에서 데이터를 꺼냄

Python 에서는 collections.deque를 사용하면 큐를 효율적으로 구현할 수 있음. deque는 양방향 큐로, 빠른 연산이 가능