[DSA][Trees] 02. Maximum Depth of Binary Tree

LeetCode 104

 

02. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 

 

[질문하기]

- 빈 트리(루트가 None)인 경우 깊이는 0으로 처리하나요?

 

[아이디어]

- BFS를 사용하여 level을 구하자

 

 

[풀이 1] Breadth First Search

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        q = deque()
        if root:
            q.append(root)

        level = 0
        while q:
            for i in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return level

트리 문제는 대부분 DFS와 BFS 모두로 해결이 가능하지만,
이 문제는 최대 깊이 = 레벨의 수를 구하는 문제이므로 BFS 방식이 더 직관적이고 명확하다고 생각한다.

 

물론, DFS를 사용해 왼쪽과 오른쪽 서브트리의 깊이를 재귀적으로 구한 뒤 max(left, right) + 1 방식으로도 구현이 가능하다.

 

⏱️ 시간복잡도

이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

노드를 순회하기 위해 큐(deque)를 사용하는 BFS 방식이므로, 최악의 경우 큐에 최대 한 레벨의 모든 노드가 저장될 수 있다. 따라서 공간 복잡도는 O(w)이며, 여기서 w는 트리의 최대 너비(가장 많은 노드를 포함한 레벨의 노드 수)이다.