LeetCode: 124. Binary Tree Maximum Path Sum

At each node, we have to do two jobs.

First: update the global sum with the path going through node, node's left child, and node's right child

Second: either choose node's left child or node's right child to return a partial path than can be connected to current node's parent

- here we can't choose both left child and right child because if we choose both of them, that path can't be connected to current node's parent

# 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 = -float('inf')
        self.dfs(root)
        return self.max
        
    def dfs(self, root):
        if not root:
            return 0
        left, right = self.dfs(root.left), self.dfs(root.right)
        ret = root.val
        if left > 0 and right > 0:
            ret += max(left, right)
        elif left > 0 and right <= 0:
            ret += left
        elif left <= 0 and right > 0:
            ret += right
        self.max = max(self.max, root.val+max(0, left)+max(0, right))
        return ret

 

Simpler solution:

dfs function will iterate through all nodes once.
The function will return max value (from the sub tree of which the node is the root) that can be concatenated to its parent node while updating self.ret with maximum value (that can be achieved by the subtree).

Consider below cases

1. self.dfs(left) + node.val + self.dfs(right) : this case penetrates the node. update self.ret, but it cannot be concatenated to its parent.
2. node.val + self.dfs(left) : this case can be concatenated to its parent. update self.ret and return the value if it is max
3. node.val + self.dfs(right) : same as (2)
4. node.val : should be considered too and it can be concatenated as well.

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.ret = -float('inf')
        self.dfs(root)
        return self.ret
        
    def dfs(self, node):
        if not node:
            return 0
        left, right = self.dfs(node.left), self.dfs(node.right)
        self.ret = max(self.ret, node.val, node.val+left, node.val+right, node.val+left+right)
        return max(node.val, node.val+left, node.val+right)