이진 트리의 최소 공통 조상(LCA)이란?
이진 트리가 주어졌을 때, 두 노드의 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾는 문제를 살펴보겠습니다. 두 노드 p와 q의 LCA란, p와 q를 모두 자손(descendant)으로 가지면서 트리에서 가장 아래쪽에 위치한 노드를 의미합니다.
예를 들어 이진 트리가 [3,5,1,6,2,0,8,null,null,7,4]로 구성되어 있다면 트리는 다음과 같은 형태가 됩니다.
위 트리에서 5와 1의 LCA는 3입니다.
문제 해결 접근 방법
이 문제는 재귀 호출을 활용하면 깔끔하게 해결할 수 있습니다. 알고리즘의 핵심 단계는 다음과 같습니다.
- 트리(현재 노드)가 비어 있다면 null을 반환합니다.
- 현재 루트 노드의 값이 p 또는 q와 같다면 해당 루트를 반환합니다.
- left := 왼쪽 서브트리에서 p와 q의 LCA를 재귀적으로 구합니다.
- right := 오른쪽 서브트리에서 p와 q의 LCA를 재귀적으로 구합니다.
- left와 right가 모두 null이 아니라면, p와 q가 서로 다른 서브트리에 분포해 있다는 뜻이므로 현재 루트가 LCA입니다. 따라서 루트를 반환합니다.
- 그렇지 않다면 left와 right 중 null이 아닌 쪽을 그대로 반환합니다.
핵심 아이디어는 간단합니다. 어떤 노드를 기준으로 왼쪽과 오른쪽 양쪽에서 각각 대상 노드가 발견된다면, 그 노드가 바로 두 노드가 만나는 지점, 즉 최소 공통 조상이라는 것입니다.
Python 구현 예제
아래 코드는 위 알고리즘을 실제로 구현한 것입니다. 트리 생성을 위한 헬퍼 함수와 함께 LCA를 구하는 Solution 클래스를 포함하고 있습니다.
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 lowestCommonAncestor(self, root, p, q):
if not root:
return None
if root.data == p or root.data == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if right and left:
return root
return right or left
ob1 = Solution()
tree = make_tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
print(ob1.lowestCommonAncestor(tree, 5, 1).data)입력
[3,5,1,6,2,0,8,null,null,7,4] 5 1
출력
3
시간 복잡도 및 특징 정리
- 시간 복잡도: O(n) — 트리의 모든 노드를 최악의 경우 한 번씩 방문합니다.
- 공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이 h에 비례합니다. 균형 잡힌 트리라면 O(log n)입니다.
이 알고리즘은 이진 탐색 트리(BST)가 아닌 일반 이진 트리에서도 동작하며, 노드 값의 순서나 중복 여부에 제약받지 않는다는 장점이 있습니다. 재귀적 후위 순회(post-order traversal)의 전형적인 응용 사례이므로, 코딩 인터뷰에서도 자주 출제되는 유형입니다.