[Leetcode 124] - Binary Tree Maximum Path Sum w/ Python

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.

 

 

 

이진 트리가 주어졌을때 최대 값을 만드는 길이를 구하는 문제

즉 노드마다 Value가 있을때 트리에서 노드를 이어서 최대 값을 비교한뒤 가장 큰 길이의 값을 리턴

 

 

 

https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

 

 

 

---

 

 

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.

 

 

 

 

---

 

 

 

 

가장 크게 유의할 점은 바로 음수 처리인것 같다

 

결국 노드의 값이 음수고, 더한 값이 음수로 나온다면 알고리즘 전체가 안돌아갈수도 있다

결국 Child 노드에서 Parent 노드한테 음수를 보낸다면 부모 노드에서 이를 0 처리 하여 계산을 계속해서 해결했다

 

 

---

 

 

1. 노드가 None일때 까지 탐색 → 0 리턴

2. 왼쪽 값, 현재 노드 값, 오른쪽 값을 더한 다음 현재 최대 값이랑 비교해서 저장

※ 위에 말한대로 여기에서 왼쪽 또는 오른쪽 값이 음수라면 아예 0 처리를 해버린다

(노드 자체가 더하기에 도움이 안된다라고 생각하면 길이에 포함이 안된다고 판단)

3. 왼쪽 값, 오른쪽 값중에서 더 값이 큰 면을 부모 노드한테 보낸다

※ 부모 노드한테 가면 어차피 한면 길이 만 사용 가능

 

 

class Solution:
    def maxPathSum(self, root):
        ans = root.val

        def dfs(root):
            if not root: return 0

            left = max(dfs(root.left), 0)
            right = max(dfs(root.right), 0)

            nonlocal ans
            ans = max(ans, root.val + left + right)

            return root.val + max(left, right)
        
        dfs(root)
        return ans