Python으로 이진 트리의 가장 깊은 리프 노드 최소 공통 조상(LCA) 구하기

루트가 있는 이진 트리가 주어졌을 때, 가장 깊은 리프(잎) 노드들의 최소 공통 조상(Lowest Common Ancestor, LCA)을 반환하는 문제입니다. 문제를 풀기 전에 다음 세 가지 정의를 먼저 이해해야 합니다.

기본 개념 정리

이진 트리에서 리프 노드란 자식 노드를 하나도 가지지 않는 노드를 의미합니다.
루트 노드의 깊이는 0이며, 어떤 노드의 깊이가 d라면 그 노드의 자식 노드들은 모두 깊이 d+1을 가집니다.
노드 집합 S의 최소 공통 조상이란, S에 속한 모든 노드를 자신의 서브트리 안에 포함하면서 깊이가 가장 큰(가장 아래에 있는) 노드 A를 말합니다.

문제 예시

예를 들어 입력이 [1,2,3,4,5]로 구성된 트리라고 가정해 보겠습니다.

Python으로 이진 트리의 가장 깊은 리프 노드 최소 공통 조상(LCA) 구하기

이 경우 가장 깊은 리프 노드는 4와 5이며, 두 노드의 최소 공통 조상은 2입니다. 따라서 출력 결과는 [2,4,5]가 됩니다.

풀이 접근 방법

이 문제는 재귀적으로 해결할 수 있습니다. 핵심 아이디어는 각 노드마다 "해당 서브트리의 최대 깊이"와 "그 깊이에 해당하는 LCA 후보 노드"를 함께 반환하는 것입니다.

solve() 메서드 설계

solve(node) 메서드를 정의합니다. 각 단계는 다음과 같이 동작합니다.
노드가 존재하지 않으면 [0, None]을 반환합니다. (깊이 0, 조상 없음)
노드의 왼쪽과 오른쪽 서브트리가 모두 비어 있다면, 즉 리프 노드라면 [1, node]를 반환합니다.
그렇지 않으면 왼쪽과 오른쪽 서브트리에 대해 재귀 호출합니다.
d1, l = solve(node.left), d2, r = solve(node.right)
d1 > d2라면 더 깊은 쪽인 왼쪽의 결과를 사용하여 [d1 + 1, l]을 반환합니다.
d2 > d1이라면 마찬가지로 [d2 + 1, r]을 반환합니다.
양쪽 깊이가 같다면 현재 노드가 두 서브트리의 공통 조상이 되므로 [d1 + 1, node]를 반환합니다.

메인 로직

result = solve(root)를 호출합니다.
결과 리스트의 두 번째 값 result[1], 즉 LCA 노드를 반환합니다.

Python 구현 코드

아래는 전체 동작 과정을 이해하기 쉽도록 작성한 Python 구현 예제입니다.

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 print_tree(root):
    # 중위 순회(inorder traversal)로 출력
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution(object):
    def lcaDeepestLeaves(self, root):
        return self.solve(root)[1]

    def solve(self, node):
        if not node:
            return [0, None]
        if not node.left and not node.right:
            return [1, node]
        d1, l = self.solve(node.left)
        d2, r = self.solve(node.right)
        if d1 > d2:
            return [d1 + 1, l]
        elif d2 > d1:
            return [d2 + 1, r]
        return [d1 + 1, node]

ob = Solution()
root = make_tree([1, 2, 3, 4, 5])
print_tree(ob.lcaDeepestLeaves(root))

실행 결과 확인

입력

[1,2,3,4,5]

출력

4, 2, 5,

출력 결과를 보면 LCA 노드 2를 루트로 하는 서브트리가 중위 순회 방식으로 4, 2, 5 순서로 출력되었음을 확인할 수 있습니다. 즉, 노드 4와 5의 최소 공통 조상인 노드 2가 올바르게 반환된 것입니다.

복잡도 분석

시간 복잡도: O(N) — 트리의 모든 노드를 한 번씩 방문합니다.
공간 복잡도: O(H) — 재귀 호출 스택의 깊이는 트리의 높이 H에 비례합니다. (H는 최악의 경우 N)