[LeetCode][python3]Day29. Binary Tree Maximum Path Sum (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.30

1. My solution

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        self.maxpath = root.val
        def depth(node):
            if not node: return 0
            L = depth(node.left)
            R = depth(node.right)
            # path
            tmp=max([L,R,L+R])
            self.maxpath = max(self.maxpath, tmp+node.val)
            return max([L,R,0]) + node.val
        
        return max(depth(root),self.maxpath)

Explanation:

Same logic with the question “Diameter of Binary Tree” in day 11. Every node can decide one of the values to return to parent’s node [self, self+L, self+R]. Since each path must have an one node and the only node (I call it head node) in the path which its parent node is not in the path, we calculate the maxpath in every node for the situation “the max when the node is the header node”.