이진 트리(Binary Tree)가 하나 주어졌을 때, 해당 트리의 최대 깊이(Maximum Depth)를 구하는 것이 이번 글의 목표입니다. 여기서 최대 깊이란 루트(Root) 노드에서 출발하여 가장 긴 경로를 따라 리프(Leaf) 노드에 도달할 때까지 거치는 노드 수의 최댓값을 의미합니다.
예를 들어 위 그림과 같은 트리가 있다면, 루트에서 리프까지 가장 긴 경로가 지나는 노드는 총 3개이므로 최대 깊이는 3이 됩니다.
해결 접근 방법
이 문제는 재귀(Recursion)를 활용하면 매우 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 재귀 함수
solve(root, depth = 0)를 정의합니다. - 현재 노드가 비어 있다면(None이라면) 지금까지 누적된
depth를 그대로 반환합니다. - 그렇지 않다면 왼쪽 서브트리와 오른쪽 서브트리에 대해 각각
depth + 1을 인자로 재귀 호출하고, 두 결과 중 더 큰 값을 반환합니다.
즉, 트리를 따라 내려갈 때마다 깊이를 하나씩 증가시키고, 리프에 도달하면 누적된 깊이를 반환한 뒤, 좌우 서브트리의 결과 중 최댓값이 곧 전체 트리의 최대 깊이가 되는 원리입니다.
구현 예제
아래 코드를 통해 더 자세히 살펴보겠습니다.
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return self.solve(root)
def solve(self,root,depth = 0):
if root == None:
return depth
return max(self.solve(root.left,depth+1),self.solve(root.right,depth+1))
tree1 = make_tree([1,2,2,3,4,None,3])
ob1 = Solution()
print(ob1.maxDepth(tree1))입력
tree1 = make_tree([1,2,2,3,4,None,3])
출력
3
실행 결과 분석
입력 리스트 [1,2,2,3,4,None,3]로 구성한 트리에서 루트 노드(1)부터 가장 깊은 리프 노드(3 또는 4)까지의 경로는 루트 → 자식 → 손자 순으로 3개의 노드를 거칩니다. 따라서 프로그램은 3을 출력합니다.
시간 및 공간 복잡도
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)(n은 노드 수)입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되며, 트리의 높이 h에 비례하므로 O(h)입니다. 다만 트리가 한쪽으로 치우쳐 있어 높이가 n과 같아지는 최악의 경우에는 O(n)까지 증가할 수 있습니다.