Path with Maximum Sum (hard)

1. Keep in mind that you need to check path every node. Not every leaf as it was in before problem.
2. Consider if you need to sum a negative path.

lass Solution:
  
  def dfs(self, node):
    if not node:
      return 0

    left = self.dfs(node.left)
    right = self.dfs(node.right)

    path = 0 
    if right > 0 and left < 0:
      path = right + node.val
    elif left > 0 and right < 0:
      path = left + node.val
    else: 
      path = left + right + node.val

    self.max_path = max(self.max_path, path)

    return max(left, right) + node.val

  def findMaximumPathSum(self, root):
    self.max_path = root.val
    self.dfs(root)
    return self.max_path