_124. Binary Tree Maximum Path Sum.md

124. Binary Tree Maximum Path Sum

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 04, 2024

Last updated : July 04, 2024

---

Related Topics : Dynamic Programming, Tree, Depth-First Search, Binary Tree

Acceptance Rate : 40.5 %

---

Solutions

• h124.py

Python

h124.py

# 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: Optional[TreeNode]) -> int:
        # Schema: (longest independent, longestChain)
        def helper(curr: Optional[TreeNode]) -> Tuple[int, int] :
            if not curr :
                return (None, None)
            if not curr.left and not curr.right :
                return (curr.val, curr.val)

            leftInd, leftChn = helper(curr.left)
            rightInd, rightChn = helper(curr.right)

            independentCandidates = [curr.val]
            chainCandidates = [0]
            if leftInd != None :
                independentCandidates.append(leftInd)
                independentCandidates[0] += max(0, leftChn)
                chainCandidates.append(leftChn)
            if rightInd != None :
                independentCandidates.append(rightInd)
                independentCandidates[0] += max(0, rightChn)
                chainCandidates.append(rightChn)

            return (max(independentCandidates), max(chainCandidates) + curr.val)
        return max(helper(root))