Leetcode 124 Binary Tree Maximum Path Sum

Soru

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.

Örnek 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.

Örnek 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.

Çözüm

• Bir binary tree veriliyor ve bu ağaçtaki herhangi bir başlangıç ve bitiş düğümü arasında giden bir path’in toplam değeri isteniyor. Bu path, bir node’dan aşağı veya yukarı doğru gidebilir ama bir node’u sadece bir kez içerebilir.
• Path’in root’tan başlaması gerekmez.
• Çözüm Stratejisi:
• Her node’da:Sol alt ağaçtan ve sağ alt ağaçtan gelen maksimum path sum’u al.
• Bu node’u içeren toplam yolu: left + node.val + right şeklinde düşün.
• Ama üst node’a dönerken ya sola ya sağa devam edebilirsin. Yani sadece node.val + max(left, right) dönülür.
• Her adımda global maksimumu güncelle.

Code

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')

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

            # Negatif katkı yapan path'leri yok say
            left = max(dfs(node.left), 0)
            right = max(dfs(node.right), 0)

            # Şu anki node'dan geçen en iyi yol
            current_max = node.val + left + right

            # Global max'ı güncelle
            self.max_sum = max(self.max_sum, current_max)

            # Parent'a dönecek path (sadece bir yön seçilebilir)
            return node.val + max(left, right)

        dfs(root)
        return self.max_sum


                

Complexity

• Time complexity (Zaman Karmaşıklığı) :O(n)
• Space complexity (Alan Karmaşıklığı) :O(h) (h: ağacın yüksekliği)