이진 트리가 주어졌을 때, 주어진 두 노드의 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾는 문제입니다. 두 노드 p와 q의 LCA란, 트리 전체에서 p와 q를 모두 자손으로 가지면서 가장 깊은(낮은) 위치에 있는 노드를 의미합니다.
예를 들어 이진 트리가 [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]와 같이 구성되어 있다면, 트리의 구조는 다음과 같습니다.
위 트리에서 노드 2와 노드 8의 LCA는 6입니다. 두 노드 모두 6을 조상으로 가지며, 그보다 더 깊은 노드 중에서는 두 노드를 동시에 포함하는 조상이 없기 때문입니다.
문제 해결 접근 방법
이 문제는 재귀적으로 해결할 수 있으며, 단계는 다음과 같습니다.
- 트리가 비어 있다면 null을 반환합니다.
- p 또는 q가 루트 노드와 같다면 루트를 반환합니다.
- left := 루트의 왼쪽 서브트리에 대해 p와 q의 LCA를 재귀적으로 구합니다.
- right := 루트의 오른쪽 서브트리에 대해 p와 q의 LCA를 재귀적으로 구합니다.
- left와 right가 모두 null이 아니라면, p와 q가 서로 다른 서브트리에 존재한다는 뜻이므로 현재 루트가 LCA입니다. 따라서 루트를 반환합니다.
- 그렇지 않다면 left 또는 right 중 null이 아닌 값을 반환합니다.
구현 예제
다음 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
class Solution():
def lowestCommonAncestor(self, root, p, q):
if not root:
return None
if p == root or q==root:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or 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
def search_node(root, element):
if (root == 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
root = make_tree([6,2,8,0,4,7,9,None,None,3,5])
ob1 = Solution()
op = ob1.lowestCommonAncestor(root, search_node(root, 2), search_node(root, 8))
print(op.data)
입력
[6,2,8,0,4,7,9,null,null,3,5]
2
8
출력
6
동작 원리 및 복잡도
이 알고리즘은 트리를 후위 순회(post-order)하며 각 노드에서 p와 q를 발견했는지 확인합니다. 왼쪽과 오른쪽 서브트리 양쪽에서 각각 하나씩 노드가 발견되면 그 지점의 노드가 바로 최소 공통 조상이 됩니다. 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)이며, 공간 복잡도는 재귀 호출 스택의 깊이에 따라 최악의 경우 O(n)입니다.