124.md

124. Binary Tree Maximum Path Sum

Given a 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.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

my thoughts:

1. dfs and update max.

my solution:

**********
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        if not root.left and not root.right:
            return root.val
        
        self.max = root.val
        def helper(root):
            if not root:
                return 0
            if not root.left and not root.right:
                if root.val>self.max:
                    self.max = root.val
                return root.val
            left = helper(root.left)
            right = helper(root.right)
            route = max(root.val, root.val+left, root.val+right, root.val+left+right)
            path = max(root.val, root.val+left, root.val+right)
            if route > self.max:
                self.max = route
            return path
            
        helper(root)
        return self.max

my comments:

from other ppl's solution:

1. N/A