[DSA][Trees] 14. Binary Tree Maximum Path Sum

LeetCode 124

 

14. Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them.
A node can only appear in the sequence at most once.
Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node's values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.

 

 

[질문하기]

- 한 노드에서 시작해서 그 노드에서 끝나는 경로도 유효한가요? YES

- 노드 값이 음수일 수도 있나요? YES

 

[아이디어]

- 각 노드에서 왼쪽/오른쪽의 재귀를 통해 최대 경로 합을 계산해 전체 경로 합을 갱신하고, 한 방향(왼쪽 또는 오른쪽)의 path를 선택해 반환한다.

 

 

[풀이 1] Depth First Search

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        res = [root.val]

        def dfs(root):
            if not root:
                return 0
            
            leftMax = dfs(root.left)
            rightMax = dfs(root.right)
            leftMax = max(leftMax, 0)
            rightMax = max(rightMax, 0)

            res[0] = max(res[0], root.val + leftMax + rightMax)
            return root.val + max(leftMax, rightMax)
        
        dfs(root)
        return res[0]

특정 노드를 기준으로 "해당 노드를 루트로 하는 하나의 경로"를 생각해 보면, 최대 경로의 합은 (왼쪽 서브트리에서의 최대 경로 합 + 현재 노드의 값 + 오른쪽 서브트리에서의 최대 경로 합)으로 정의할 수 있다. 따라서 최대 합을 가지는 경로를 구할 때는, 재귀를 통해 왼쪽과 오른쪽 자식으로부터 최대 경로 합을 각각 전달받고, 그 둘을 현재 노드의 값과 더해 최댓값을 갱신하면 된다.

 

하지만 재귀적으로 자식 노드로부터 부모 노드로 값을 반환할 때는, 왼쪽 혹은 오른쪽 중 하나의 방향만 선택해야 한다. 왜냐하면 경로는 사이클 없이 한 방향으로만 연결된 연속된 노드들의 집합이기 때문에, 부모 노드가 양쪽 자식으로 동시에 이어지는 경로를 선택할 수는 없기 때문이다. 따라서 재귀 함수에서는 max(왼쪽 서브트리의 최댓값, 오른쪽 서브트리의 최댓값) + 현재 노드의 값을 부모 노드로 반환해야 한다. 이렇게 하면 부모 노드는 왼쪽 혹은 오른쪽 중 더 큰 값을 선택해서, 자신의 값과 함께 한 방향으로 경로를 이을 수 있게 된다.

 

즉, Diameter of Binary Tree 문제처럼, 이 문제에서도 재귀 함수 하나가 두 가지 역할을 수행해야 한다.

1. 현재 노드를 포함해서 만들 수 있는 전체 경로의 최댓값 계산 (양쪽 자식 포함 가능)
2. 현재 노드를 루트로 해서 부모로 전달할 수 있는 단일 경로의 최대값 반환 (왼쪽 or 오른쪽만 선택)

2025.07.12 - [자료구조와 알고리즘] - [DSA][Trees] 03. Diameter of Binary Tree

 

또한 한 가지 중요한 점은, 왼쪽이나 오른쪽 서브트리에서 전달된 경로 합이 음수라면, 그 경로를 포함하는 것이 오히려 전체 합을 줄이게 된다. 따라서 이런 경우에는 해당 경로를 선택하지 않는 것이 낫기 때문에, 재귀 호출 시 음수는 0으로 처리하여 최댓값 계산에서 제외한다.

 

⏱️ 시간복잡도

트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되기 때문에 O(h)에 비례하고 따라서 공간 복잡도는 최악의 경우 O(N) (Skew 트리)이고, 평균적으로는 O(log N) (균형 잡힌 트리)이다.