파이썬으로 이진 트리 루트-리프 경로의 최대 합 구하기

이진 트리(binary tree)가 주어졌을 때, 루트 노드에서 리프 노드까지 이어지는 모든 경로 중 합이 가장 큰 값을 찾아야 합니다.

문제 예시

예를 들어 아래와 같은 트리가 입력으로 주어진다고 가정해 보겠습니다.

루트에서 출발하여 5 → 9 → 7 → 8 순서로 경로를 따라 내려가면 각 노드의 값을 모두 더한 결과가 29가 되므로, 출력은 29입니다.

풀이 접근 방법

이 문제는 깊이 우선 탐색(DFS)을 활용한 재귀 함수로 간단하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

walk() 함수를 정의합니다. 이 함수는 노드(node)와 누적합(s)을 매개변수로 받습니다.
노드가 null(빈 값)인 경우:
- max_sum을 기존 max_sum과 s 중 더 큰 값으로 갱신합니다.
- 함수를 종료(return)합니다.
s에 현재 노드의 데이터 값을 더합니다.
노드의 왼쪽 자식에 대해 walk(left, s)를 재귀 호출합니다.
노드의 오른쪽 자식에 대해 walk(right, s)를 재귀 호출합니다.
메인 메소드(solve)에서는 다음을 수행합니다.
- max_sum을 0으로 초기화합니다.
- walk(root, 0)을 호출합니다.
- max_sum을 반환합니다.

구현 예제

아래 코드를 통해 더 쉽게 이해할 수 있습니다.

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

class Solution:
    def walk(self, node, s):
        if not node:
            self.max_sum = max(self.max_sum, s)
            return
        s += node.data
        self.walk(node.left, s)
        self.walk(node.right, s)

    def solve(self, root):
        self.max_sum = 0
        self.walk(root, 0)
        return self.max_sum

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

입력

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)

출력

동작 원리 정리

이 알고리즘은 트리의 모든 루트-리프 경로를 한 번씩 순회하면서 각 경로의 누적합을 계산하고, 그중 가장 큰 값을 max_sum에 저장합니다. 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)(n은 노드 수)이며, 재귀 호출 스택을 고려한 공간 복잡도 역시 O(n)입니다. 음수 값을 포함하는 트리라면 max_sum 초기값을 0 대신 매우 작은 값(-무한대)으로 설정하는 것이 안전합니다.