124. 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 path.

해도해도 안되는 트리 노답자라서 루션이 봤읍니다

Solution 1: Runtime: 80 ms - 92.20% / Memory Usage: 21 MB - 91.44%

# 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: TreeNode) -> int:
        self.res = float('-inf')
        self.helper(root)
        return self.res 
        
    def helper(self, root):
        if not root:
            return 0
        left, right = self.helper(root.left), self.helper(root.right)
        self.res = max(self.res, root.val + left + right)
        return max(root.val + max(left, right), 0)

helper 재귀를 이용

left, right = self.helper(root.left), self.helper(root.right)
여기서 재귀를 타고 가다보면 결국엔 루트의 왼쪽, 오른쪽 값들의 여러 조합 중에 가장 큰 합을 얻게 됨

self.res = max(self.res, root.val + left + right)
이걸로 자동으로 최댓값이 업데이트 되고...

거의 티비 속에 티비 속에 티비... 처럼 액자식 구성이라.. 이해가 잘 된건지 만건지..^^