파이썬 이진 트리에서 두 노드의 최저 공통 조상(LCA) 찾기 – 재귀 알고리즘 구현 가이드

이진 트리와 두 개의 숫자 a, b가 주어졌을 때, a와 b를 자손(descendant)으로 가지는 노드 중 가장 깊은 위치에 있는 노드의 값을 찾는 것이 목표입니다. 이런 노드를 최저 공통 조상(Lowest Common Ancestor, LCA)이라고 부릅니다. 이때 한 노드는 스스로의 자손이 될 수 있다는 점에 유의해야 합니다.

예를 들어 아래와 같은 이진 트리가 있다고 가정해 보겠습니다.

a = 6, b = 2라면, 두 값을 모두 자손으로 가지면서 가장 깊은 노드는 값이 4인 노드입니다. 따라서 출력 결과는 4가 됩니다.

해결 전략: 재귀적 탐색

이 문제는 재귀(DFS) 기반 탐색으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 각 노드를 기준으로 왼쪽과 오른쪽 서브트리에서 a 또는 b를 찾았는지 확인하고, 양쪽 모두에서 발견되는 첫 번째 지점이 곧 최저 공통 조상이라는 것입니다. 구체적인 동작 순서는 다음과 같습니다.

1. solve() 메서드를 정의합니다. 이 메서드는 루트 노드와 두 값 a, b를 매개변수로 받습니다.
2. 루트가 null이면 -1을 반환합니다. (대상 노드를 찾지 못했다는 신호)
3. 루트의 값이 a 또는 b와 일치하면 해당 값을 반환합니다. 노드는 자기 자신의 조상이 될 수 있으므로 이 단계가 중요합니다.
4. 왼쪽 서브트리에 대한 solve(root.left, a, b)의 결과를 left에 저장합니다.
5. 오른쪽 서브트리에 대한 solve(root.right, a, b)의 결과를 right에 저장합니다.
6. left와 right가 모두 -1이 아니라면 현재 노드의 값을 반환합니다. 이 노드가 바로 최저 공통 조상입니다.
7. 그 외의 경우에는 -1이 아닌 값을 그대로 위로 전달합니다. (left가 -1이 아니면 left, 아니면 right)
8. 메인 함수에서 solve(root)를 호출해 최종 결과를 얻습니다.

파이썬 구현 코드

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

class Solution:
    def solve(self, root, a, b):
        if not root:
            return -1
        if root.val in (a, b):
            return root.val
        left = self.solve(root.left, a, b)
        right = self.solve(root.right, a, b)
        if -1 not in (left, right):
            return root.val
        return left if left != -1 else right

ob = Solution()
root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root, 6, 2))

입력

root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
6, 2

출력

4

동작 원리 살펴보기

a = 6과 b = 2가 트리에서 어떻게 발견되는지 단계별로 추적해 보면 다음과 같습니다.

• 노드 8의 왼쪽 자식인 노드 6에서 a를 발견하고 6을 반환합니다.
• 노드 4의 오른쪽 자식인 노드 2에서 b를 발견하고 2를 반환합니다.
• 노드 8은 왼쪽에서만 6을 받았으므로 6을 그대로 위로 전달합니다.
• 노드 4는 왼쪽에서 6, 오른쪽에서 2를 받았습니다. 두 값이 모두 발견되는 첫 번째 지점이므로 4를 반환하고, 이것이 최종 출력이 됩니다.

시간 및 공간 복잡도

• 시간 복잡도: O(N). 최악의 경우 트리의 모든 노드를 한 번씩 방문합니다. N은 노드의 총 개수입니다.
• 공간 복잡도: O(H). 재귀 호출 스택의 깊이는 트리의 높이 H에 비례합니다. 한쪽으로 치우친 트리에서는 O(N)까지 늘어날 수 있습니다.

참고 사항

이 구현은 a와 b가 트리에 모두 존재한다고 가정합니다. 만약 둘 중 하나만 존재한다면 존재하는 노드의 값이 그대로 반환될 수 있으므로, 필요하다면 탐색 전에 두 값의 존재 여부를 먼저 검증하는 로직을 추가하는 것이 안전합니다.