124. Binary Tree Maximum Path Sum - 파이썬

문제

---

• [릿코드 링크](https://leetcode.com/problems/binary-tree-maximum-path-sum/_
• 이진트리의 각 노드를 한 번만 지날 수 있을 때 path의 최대값을 구하는 문제

풀이

---

• 난이도 hard
• 처음 풀었을 때 틀려서 다시 풀었다.
• 한 번만 지날 수 있기 때문에 결국 어느 노드에서 left와 right를 모두 포함할지 결정해야 한다.(어느 노드를 root 노드로 할지)
• path를 이어나가기 위해서는 왼쪽 혹은 오른쪽 중 하나만 선택해야 한다.
• 따라서 아래 코드를 실행하면 가장 밑에 level부터 cur_max를 갱신하게 된다.
• 밑에 있는 노드부터 차례로 path값을 계산한 후 path를 잇는 것이 더 값이 크면 이어나간다.

코드

---

class Solution:
    def maxPathSum(self, root):
        self.cur_max = float('-inf')
        self.maxval(root)
        return self.cur_max

    def maxval(self, root):
        if not root:
            return 0
        # 재귀로 돌아가기 때문에 결국 가장 밑에있는 자식노드부터 값을 체크하게 된다. 
        left = self.maxval(root.left)
        right = self.maxval(root.right)
        # left + root.val + right로 cur_max가 갱신된다면 노드를 이어나간다는 뜻 
        self.cur_max = max(self.cur_max, left + root.val + right)
        # -이면 포함시킬 필요가 없다. 
        return max(root.val + max(left, right), 0)