new_contents: """Leetcode 124. Binary Tree Maximum Path Sum
  Hard
  
  URL:
  
  Given a non-empty binary tree, find the maximum path sum.
  
  For this problem, a path is defined as any sequence of nodes from some starting
  node to any node in the tree along the parent-child connections. The path must
  contain at least one node and does not need to go through the root.
  
  Example 1:
  Input: [1,2,3]
         1
        / \
       2   3
  Output: 6
  
  Example 2:
  Input: [-10,9,20,null,null,15,7]
     -10
     / \
    9  20
      /  \
     15   7
  Output: 42
  """
  
  # Definition for a binary tree node.
  class TreeNode(object):
      def __init__(self, val):
          self.val = val
          self.left = None
          self.right = None
  
  
  class Solution(object):
      def maxPathSum(self, root):
          """
          :type root: TreeNode
          :rtype: int
          """
          pass
  
  
  def main():
      pass
  
  
  if __name__ == '__main__':
      main()
  
subject: Add lc0124_binary_tree_maximum_path_sum.py