이진 트리가 주어지고, 트리 내 여러 노드들의 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾아야 한다고 가정해 보겠습니다. 이진 트리에서 최소 공통 조상이란 노드 x1, x2, x3, ..., xn을 모두 자손으로 두는 노드 중 가장 아래에 위치한 노드를 의미합니다. 이때 한 노드가 자기 자신의 자손이 될 수도 있다는 점이 중요합니다.
입력으로는 트리의 루트 노드와 조상을 찾을 노드들의 목록이 주어지며, 우리는 해당 노드를 찾아 결과로 반환해야 합니다.
예제로 살펴보기
다음과 같은 이진 트리가 있다고 가정합니다.
찾고자 하는 노드 목록이 [6, 8]이라면 출력값은 7입니다. 노드 6과 8을 모두 자손으로 가지는 노드 중 가장 깊은 곳에 있는 노드가 바로 7이기 때문입니다.
문제 해결 접근 방식
이 문제는 재귀적 후위 순회(post-order traversal)를 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 조상을 찾을 각 값에 대해 search_node() 함수로 실제 트리 노드 객체를 찾아 집합(set)에 저장합니다.
- 재귀 함수 fn(node)를 정의합니다.
- 현재 노드가 null이면 그대로 반환합니다.
- 현재 노드가 찾는 노드 집합에 포함되어 있으면 해당 노드를 반환합니다.
- 왼쪽과 오른쪽 자식에 대해 각각 fn()을 재귀 호출합니다.
- 왼쪽과 오른쪽 결과가 모두 null이 아니라면 현재 노드가 공통 조상이므로 현재 노드를 반환합니다.
- 그렇지 않고 한쪽만 null이 아니라면 null이 아닌 쪽의 결과를 반환합니다.
파이썬 구현 코드
import collections
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
def search_node(root, element):
if root is None:
return None
if root.data == element:
return root
res1 = search_node(root.left, element)
if res1:
return res1
res2 = search_node(root.right, element)
return res2
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.data, end=', ')
print_tree(root.right)
def solve(root, node_list):
# 찾고자 하는 값을 실제 노드 객체로 변환해 집합에 저장
nodes = set()
for elem in node_list:
target = search_node(root, elem)
if target:
nodes.add(target)
# 후위 순회 기반 재귀 함수
def fn(node):
if not node:
return node
if node in nodes:
return node
left, right = fn(node.left), fn(node.right)
if left and right:
return node
return left or right
return fn(root)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, [6, 8]).data)
실행 결과
입력
make_tree([5, 3, 7, 2, 4, 6, 8]), [6, 8]
출력
7
동작 원리 상세 설명
예제 트리에서 노드 6과 8은 모두 노드 7의 자식입니다. fn() 함수가 루트(5)부터 순회를 시작하면 다음 과정을 거칩니다.
- 루트 5에서 왼쪽 서브트리(3)와 오른쪽 서브트리(7)를 각각 탐색합니다.
- 왼쪽 서브트리(3 → 2, 4)에는 6이나 8이 없으므로 null이 반환됩니다.
- 오른쪽 서브트리에서 노드 7에 도달하면, 왼쪽 자식 6이 찾는 노드 집합에 포함되어 있어 6이 반환됩니다. 마찬가지로 오른쪽 자식 8도 반환됩니다.
- 노드 7 입장에서는 왼쪽(6)과 오른쪽(8) 결과가 모두 null이 아니므로, 자기 자신인 7을 반환합니다.
- 결국 루트 5의 오른쪽 결과로 7이 전달되고, 왼쪽은 null이므로 최종 답은 7이 됩니다.
시간 복잡도
이 알고리즘은 트리의 모든 노드를 최대 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 트리의 노드 개수입니다. 재귀 호출에 사용되는 스택 공간은 트리의 높이 h에 비례하므로 공간 복잡도는 O(h)이며, 균형 잡힌 트리의 경우 O(log n), 편향된 트리의 경우 O(n)이 됩니다.