[LeetCode] 124. Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

Hard

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.

 

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

 

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 104].
• -1000 <= Node.val <= 1000

---

문제 풀이

• 이진 트리에서 만든 경로 중 가장 최대값을 가지는 값을 출력해야한다. 
• 노드는 한번만 방문할 수 있고, 루트노드를 포함하지 않아도 돈다. 
• 재귀호출을 사용해서 푸는데, 노드는 음수를 가지고 있다는것을 명심해야한다.
• 문제에서 경로라고 일컫는 것은 노드들끼리 연결되어있는 선이라고 생각할 수 있다.
• 즉, 왼쪽 자식들 중 하나를 선택하고 오른쪽 노드들 중 하나에 도착해야한다고 생각할 수 있다. 
• 예외적으로 왼쪽, 오른쪽을 선택 안할 수도 있다. 
• 예를 들어 아래의 트리가 존재할때, 최대 경로를 구한다고 가정해보자.
•      7
• -2    2    
• 여기서 7 + 2 = 9 로 답이 나와야한다. 
• 즉, 재귀호출로 현재 해당 노드 위치에서 왼쪽, 오른쪽, 현재 노드의 값을 모두 더해서 최대값을 저장하지만
• 반환할 때는, 현재 노드와 왼쪽을 선택하거나 현재 노드와 오른쪽을 선택한 노드 값의 총합을 반환한다. 
• 그리고 재귀호출에서 반환받은 값, 왼쪽, 오른쪽은 최대값 처리를 하여 선택했을때의 값 혹은 0을 선택하게 만든다. 
• 1. 재귀함수는 매번 전체 선택값의 최대 값을 정답으로 저장한다.
• 2. 현재 노드와 왼쪽, 오른쪽 노드를 선택한 값 중에 큰 값을 반환한다.
• 3. 재귀함수에서 반환 받은 값과 0을 비교하여 음수 값은 제거한다. 

소스 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.ans = float('-inf')
        def dfs(node):
            if not node:
                return 0
            
            left = max(dfs(node.left), 0)
            right = max(dfs(node.right), 0)
            
            path = left + right + node.val
            self.ans = max(self.ans, path)
            
            return node.val + max(left, right)
        
        dfs(root)
        return self.ans