파이썬 코딩테스트 강좌, 이진 트리

이진 트리는 컴퓨터 사이언스와 알고리즘에서 기본적인 자료 구조 중 하나로, 많은 문제에서 중요한 역할을 합니다. 이진 트리를 이해하고 문제를 해결할 수 있는 능력은 코딩 인터뷰에서 매우 중요하게 평가됩니다. 이번 글에서는 이진 트리와 관련된 문제 하나를 선정하여, 문제 설명과 풀이 과정을 자세히 살펴보도록 하겠습니다.

문제: 이진 트리의 최대 깊이

주어진 이진 트리의 최대 깊이를 찾는 함수를 작성하시오. 이진 트리의 깊이는 루트 노드에서 가장 깊은 리프 노드까지의 경로에 있는 노드의 수입니다. 예를 들어, 다음과 같은 이진 트리가 있다고 가정해봅시다.

이 경우, 이진 트리의 최대 깊이는 3입니다(노드 1 → 노드 2 → 노드 4 또는 노드 5). 함수의 시그니처는 다음과 같습니다:

def maxDepth(root: TreeNode) -> int:

문제 정의

입력으로 주어지는 매개변수 root는 이진 트리의 루트 노드입니다. 이 노드는 각 노드가 좌측 및 우측 자식 노드를 가리키는 포인터를 가지는 TreeNode 클래스의 인스턴스로 정의됩니다. 이진 트리가 비어 있는 경우, 깊이는 0입니다.

입력 예시

maxDepth(root)를 호출할 경우, 반환 값은 3이어야 합니다.

출력 예시

문제 풀이 접근 방법

이 문제를 해결하기 위한 접근 방법으로는 Depth-First Search (DFS) 방법을 사용할 수 있습니다. DFS 방법을 사용하여 트리의 노드를 탐색하며 각 노드에서 리프 노드까지의 깊이를 재귀적으로 계산할 수 있습니다.

1단계: TreeNode 클래스 정의

먼저, 이진 트리의 노드를 정의하는 TreeNode 클래스를 작성해야 합니다. 각 노드는 값(value)과 좌측 자식(left), 우측 자식(right) 노드를 가집니다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2단계: 최대 깊이에 대한 재귀 함수 정의

최대 깊이를 계산하기 위한 재귀 함수를 정의합니다. 재귀 호출을 사용하여 각 서브트리의 깊이를 구하고 그 중 최대 값을 선택합니다.

def maxDepth(root: TreeNode) -> int:
    # 기저 사례: 노드가 None인 경우, 깊이는 0
    if not root:
        return 0
    # 좌측 및 우측 서브트리의 깊이를 계산
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    # 현재 노드를 포함하여 최대 깊이를 반환
    return max(left_depth, right_depth) + 1

3단계: 최종 함수 구현

이제 완전한 maxDepth 함수를 구현하였습니다. 이 함수는 주어진 이진 트리의 ‘최대 깊이’를 반환합니다.

4단계: 시간 복잡도 및 공간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 이진 트리에 있는 노드의 수입니다. 모든 노드를 한번씩 방문하기 때문에, 트리의 크기에 비례한 시간 복잡도를 가집니다. 공간 복잡도는 O(h)입니다. h는 트리의 높이로, 최악의 경우에는 O(n)의 공간 복잡도를 가질 수 있으며, 균형 이진 트리에서는 O(log n)이 됩니다.

테스트 케이스

작성한 함수를 검증하기 위해 몇 가지 테스트 케이스를 작성해보겠습니다.

# 테스트 케이스 
def test_maxDepth():
    # 테스트 케이스 1
    root1 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    assert maxDepth(root1) == 3, "Test case 1 failed"
    
    # 테스트 케이스 2
    root2 = TreeNode(1)
    assert maxDepth(root2) == 1, "Test case 2 failed"
    
    # 테스트 케이스 3: 비어 있는 트리
    root3 = None
    assert maxDepth(root3) == 0, "Test case 3 failed"
    
    # 테스트 케이스 4
    root4 = TreeNode(1, TreeNode(2))
    assert maxDepth(root4) == 2, "Test case 4 failed"
    
    print("All test cases passed!")

test_maxDepth()

결론

이번 글에서는 이진 트리의 최대 깊이를 구하는 문제를 소개하고 그 해결 방법을 자세히 설명하였습니다. 이진 트리와 관련된 문제는 매우 다양하므로, 다양한 문제를 접하며 연습하는 것이 중요합니다. Algorithm Challenge와 같은 문제를 통해 실력을 더욱 향상시킬 수 있을 것입니다. 이진 트리의 개념과 DFS 탐색의 기본 원리를 이해하는 것은 코딩테스트에서 큰 도움이 됩니다. 앞으로도 더욱 다양한 알고리즘 문제를 풀어보며 실력을 기르시기를 바랍니다.