Binary tree maximum path sum


This was the first problem I did that I needed a bit of help, but once I saw that max_path state should be kept as a global variable, it made the coding much easier. I also needed the hint for max(left, 0); 0 implying that we don't take the left.

Will need to review this problem.

from typing import Optional
# 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:
        self.max_path = -1001
        return self.max_path
    # returns maxEdge
    def dfs(self, node) -> int:

        if not node:
            return 0

        left = max(self.dfs(node.left), 0)
        right = max(self.dfs(node.right), 0)
        self.max_path = max(self.max_path, left + right + node.val)
        return max(left + node.val, right + node.val)