이진 트리가 하나 주어졌을 때, 해당 트리의 지름(diameter) 길이를 계산하는 문제를 살펴보겠습니다.
이진 트리의 지름이란 트리 안에 있는 임의의 두 노드 사이에서 가장 긴 경로의 길이를 의미합니다. 여기서 중요한 점은 이 경로가 반드시 루트(root)를 거쳐야 하는 것은 아니라는 것입니다.
예를 들어 아래와 같은 트리가 있다고 가정해 보겠습니다. 경로 [4, 2, 1, 3] 또는 [5, 2, 1, 3]의 길이가 3이므로, 이 트리의 지름은 3이 됩니다.
문제 해결 접근 방식
이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 노드를 기준으로 왼쪽과 오른쪽 서브트리의 깊이를 구하고, 두 깊이의 합이 곧 해당 노드를 지나는 가장 긴 경로가 된다는 점입니다.
- DFS를 사용해 지름을 탐색하며, 정답 변수
answer를 0으로 초기화합니다. - 루트 노드를 인자로 하여
dfs(root)함수를 호출합니다. dfs(node)함수는 다음과 같이 동작합니다:- 노드가 존재하지 않으면(빈 서브트리) 0을 반환합니다.
left:= 왼쪽 서브트리에 대한 DFS 결과,right:= 오른쪽 서브트리에 대한 DFS 결과를 저장합니다.answer:= 기존answer와left + right중 더 큰 값으로 갱신합니다. (현재 노드를 지나는 최장 경로)- 상위 노드에는 자기 자신까지 포함된 깊이를 알려주어야 하므로
max(left + 1, right + 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:
temp.left = TreeNode(data)
break
else:
que.append(temp.left)
if not temp.right:
temp.right = TreeNode(data)
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 diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
self.dfs(root)
return self.ans
def dfs(self, node):
if not node:
return 0
left = self.dfs(node.left)
right = self.dfs(node.right)
self.ans = max(self.ans, left + right)
return max(left + 1, right + 1)
root = make_tree([1, 2, 3, 4, 5])
ob1 = Solution()
print(ob1.diameterOfBinaryTree(root))입력
[1,2,3,4,5]
출력
3
복잡도 분석
시간 복잡도: O(N) — 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(H) — 재귀 호출 스택의 깊이는 트리의 높이(H)에 비례합니다. 최악의 경우(편향 트리) O(N)까지 증가할 수 있습니다.