파이썬으로 이진 트리에서 두 노드 사이 경로의 최대 합 구하기

이진 트리가 주어졌을 때, 임의의 두 노드를 연결하는 경로 중 합이 가장 큰 경로의 값을 찾아야 합니다. 여기서 말하는 '경로'란 트리 내에서 어떤 노드에서 시작해 다른 노드로 끝나는 일련의 노드 연결을 의미하며, 반드시 루트를 지날 필요는 없습니다.

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

이 경우 최대 경로 합은 62이며, 해당 경로에 포함된 노드는 [12, 13, 14, 16, 7]입니다.

문제 해결 접근 방법

이 문제는 재귀적 후위 순회(post-order traversal)를 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리에서 얻을 수 있는 최대 기여 값을 계산하고, 그 값을 바탕으로 전체 결과를 갱신하는 것입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

재귀 함수 utils()를 정의합니다. 이 함수는 루트 노드를 인자로 받습니다.
루트가 null(None)이라면 0을 반환합니다.
왼쪽 자식에 대해 재귀 호출한 결과를 l에 저장합니다.
오른쪽 자식에 대해 재귀 호출한 결과를 r에 저장합니다.
max_single은 다음 두 값 중 더 큰 값입니다. 즉, (왼쪽 또는 오른쪽 중 큰 값 + 현재 노드의 값)과 현재 노드의 값 자체를 비교합니다. 이는 한쪽 방향으로만 뻗어 나가는 경로의 최댓값을 의미합니다.
max_top은 max_single과 (l + r + 현재 노드의 값) 중 더 큰 값입니다. 이는 왼쪽과 오른쪽을 모두 연결하는 꺾인 경로의 합을 의미합니다.
전역 결과 변수 res를 max_top과 비교하여 더 큰 값으로 갱신합니다.
max_single을 반환합니다. 상위 노드 입장에서는 양쪽을 모두 포함할 수 없으므로 한쪽 방향 경로만 전달됩니다.

메인 메서드에서는 다음과 같이 처리합니다.

루트가 null이면 0을 반환합니다.
res를 음의 무한대(-infinity)로 초기화합니다. 모든 노드 값이 음수인 경우에도 올바른 결과를 얻기 위함입니다.
utils(root)를 호출해 트리를 순회합니다.
최종적으로 res를 반환합니다.

파이썬 구현 예제

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

class Solution:
    def solve(self, root):
        if root is None:
            return 0
        self.res = float("-inf")
        self.utils(root)
        return self.res

    def utils(self, root):
        if root is None:
            return 0
        l = self.utils(root.left)
        r = self.utils(root.right)
        max_single = max(max(l, r) + root.val, root.val)
        max_top = max(max_single, l + r + root.val)
        self.res = max(self.res, max_top)
        return max_single

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

입력

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

출력

동작 원리 상세 설명

위 예제 트리에서 알고리즘이 어떻게 동작하는지 살펴보겠습니다. 노드 4와 7은 리프 노드이므로 각각 자기 자신의 값(4, 7)을 반환합니다. 노드 16의 입장에서는 왼쪽에서 4, 오른쪽에서 7을 받게 되며, max_single은 max(7+16, 16) = 23이 되고, max_top은 max(23, 4+7+16) = 27이 됩니다.

노드 14에서는 왼쪽에서 23, 오른쪽에서 22를 받으므로 max_top은 23+22+14 = 59가 계산됩니다. 마지막으로 루트인 노드 13에서 왼쪽 경로(12)와 오른쪽 경로(23)를 연결하면 12+13+23 = 48이 되지만, 노드 14 하위에서 이미 27 + 13 + 12 = 52... 와 같은 조합들이 평가되며, 최종적으로 노드 12 → 13 → 14 → 16 → 7로 이어지는 경로의 합 62가 최댓값으로 기록됩니다.

시간 복잡도

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 공간 복잡도는 재귀 호출 스택 깊이에 의해 결정되며, 편향된 트리의 경우 최악 O(n), 균형 잡힌 트리의 경우 O(log n)입니다.