Maximum Depth of Binary Tree

문제 링크

• https://leetcode.com/problems/maximum-depth-of-binary-tree/

문제 설명

이진 트리의 루트 노드가 주어질 때, 이 트리의 최대 깊이를 반환하는 함수를 작성하세요. 이진 트리의 최대 깊이는 루트 노드에서 가장 먼 잎 노드까지의 경로에 있는 노드의 수를 의미합니다.

예제

• 예제 1
  • 입력: root = [3,9,20,null,null,15,7]
  • 출력: 3
  • 설명: 트리의 구조는 다음과 같습니다.

            3
           / \
          9  20
             / \
            15  7

    최대 깊이는 3입니다 (3 → 20 → 15 또는 3 → 20 → 7).
• 예제 2
  • 입력: root = [1,null,2]
  • 출력: 2
  • 설명: 트리의 구조는 다음과 같습니다.

        1
         \
          2

    최대 깊이는 2입니다 (1 → 2).

풀이 전략

이진 트리의 최대 깊이를 계산하는 방법에는 여러 가지가 있지만, 대표적인 두 가지 방법은 다음과 같습니다.

1. 재귀적 접근:
   • 트리를 탐색하면서 각 노드의 깊이를 재귀적으로 계산합니다.
   • 자식 노드에 대해 깊이를 계산하고, 그 중 더 깊은 값을 선택하여 현재 노드의 깊이를 계산합니다.
2. Iterative 접근 (BFS):
   • 큐를 사용하여 너비 우선 탐색(BFS) 방식으로 트리를 탐색합니다.
   • 각 레벨을 탐색할 때마다 깊이를 증가시키고, 다음 레벨의 노드들을 큐에 추가합니다.

코드 분석

1. 재귀적 접근

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        else:
            left_depth = self.maxDepth(root.left)  # 왼쪽 서브트리의 깊이
            right_depth = self.maxDepth(root.right)  # 오른쪽 서브트리의 깊이
            return max(left_depth, right_depth) + 1  # 현재 노드 깊이 포함

• 동작 원리:
  • 함수가 호출되면, 현재 노드가 None인 경우 0을 반환하여 리프 노드에 도달했음을 나타냅니다.
  • 현재 노드가 None이 아닐 경우, 왼쪽 및 오른쪽 서브트리의 깊이를 각각 재귀적으로 계산합니다.
  • 왼쪽과 오른쪽 서브트리 깊이 중 더 큰 값을 선택하고, 현재 노드를 포함하기 위해 1을 더하여 반환합니다.
• 시간 복잡도: (O(n)) - 트리의 모든 노드를 한 번씩 방문합니다.
• 공간 복잡도: (O(h)) - 재귀 호출 스택의 깊이는 트리의 높이에 비례하며, 최악의 경우 (h)는 (n)과 같을 수 있습니다 (편향 트리).

2. Iterative 접근 (BFS)

from collections import deque

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        queue = deque([root])
        depth = 0

        while queue:
            depth += 1  # 현재 레벨의 깊이 증가
            for _ in range(len(queue)):
                node = queue.popleft()  # 큐에서 노드 제거
                if node.left:
                    queue.append(node.left)  # 왼쪽 자식 추가
                if node.right:
                    queue.append(node.right)  # 오른쪽 자식 추가

        return depth

• 동작 원리:
  • 먼저, 루트 노드가 없으면 깊이는 0으로 반환합니다.
  • 큐에 루트 노드를 추가하고, 깊이를 0으로 초기화합니다.
  • 큐가 비어 있지 않은 동안 반복하여 각 레벨의 노드 수만큼 반복합니다. 이 때 깊이를 1씩 증가시킵니다.
  • 현재 레벨의 모든 노드를 탐색하며, 각 노드의 자식을 큐에 추가합니다.
  • 반복이 끝나면 총 깊이를 반환합니다.
• 시간 복잡도: (O(n)) - 모든 노드를 방문합니다.
• 공간 복잡도: (O(w)) - 큐의 최대 너비 (w)는 트리의 최악의 경우에 따라 다르며, 균형 트리에서는 (O(n))이 될 수 있습니다.

요약

• 이진 트리의 최대 깊이를 구하는 문제로, 재귀적 접근과 Iterative 접근 (BFS) 두 가지 방법으로 해결할 수 있습니다.
• 재귀적 접근은 구현이 간단하며 깊이를 직관적으로 이해할 수 있지만, 깊은 트리에서는 스택 오버플로우가 발생할 수 있습니다.
• Iterative 접근은 BFS를 사용하여 모든 노드를 탐색하며, 공간 사용 측면에서 균형 트리에 유리합니다.