[leetcode] 124. Binary Tree Maximum Path Sum

문제 설명

링크
이진트리의 경로들 중 path 의 합이 최대가 되는 경우를 구하는 문제

접근

• diameter of binary tree 문제와 비슷하게 접근
• left, right, left + root, root, right + root, left + right + root 판별

코드

class Solution:
    answer = 0
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.answer = float("-inf")
        self.dfs(root)
        return self.answer
    def dfs(self, root) -> int:
        if not root:
            return 0
        res = [root.val]

        l = max(self.dfs(root.left), 0) # 0 과의 비교가 중요함
        r = max(self.dfs(root.right), 0)

        self.answer = max(self.answer, l + r + root.val)
        return max(root.val, root.val + max(l, r))