[알고리즘] Lowest Common Ancestor

Lowest Common Ancestor

트리 자료구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘으로, 일반적으로 이진 트리나 이진 탐색 트리에서 사용됩니다. 재귀적인 방법과 반복문을 사용한 방법으로 구현할 수 있는데 이 포스팅에서는 재귀를 바탕으로 설명하겠습니다.

 

동작 순서

1. 루트(root)부터 시작하여 두 대상 노드의 값을 비교합니다.
2. 현재 노드의 값이 두 대상 노드의 값보다 크면, LCA는 현재 노드의 왼쪽 서브트리에 있을 것입니다. 따라서 왼쪽 자식 노드로 재귀 호출합니다.
3. 현재 노드의 값이 두 대상 노드의 값보다 작으면, LCA는 현재 노드의 오른쪽 서브트리에 있을 것입니다. 따라서 오른쪽 자식 노드로 재귀 호출합니다.
4. 두 대상 노드의 값이 현재 노드의 값과 같거나, 현재 노드의 값이 두 대상 노드의 값 사이에 있으면, 현재 노드가 LCA가 됩니다.

파이썬 예시

다음은 이진 트리에서 두 노드의 Lowest Common Ancestor를 찾는 재귀적인 알고리즘의 예시 코드입니다:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_lca(root, node1, node2):
    if root is None:
        return None
    
    if root.val > node1.val and root.val > node2.val:
        return find_lca(root.left, node1, node2)
    elif root.val < node1.val and root.val < node2.val:
        return find_lca(root.right, node1, node2)
    else:
        return root

# 예시 이진 트리 생성
#      6
#    /   \
#   2     8
#  / \   / \
# 0   4 7   9
#    / \
#   3   5
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)

node1 = TreeNode(0)
node2 = TreeNode(5)

# LCA 찾기
lca = find_lca(root, node1, node2)
print("Lowest Common Ancestor:", lca.val) # 2