[leetcode]Binary Tree Maximum Path Sum @ Python

原題住所:https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
タイトル:
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:Given the below binary tree,

       1
      / \
     2   3

 
Return  6 .
この問題は木の中で1本の経路を探して、この経路の上のノードの和は最大で、起点と終点は木の中のノードであればいいです.ここで注意しなければならないのは、ノード値が負の値になる可能性があることです.この二叉木の問題を解決するにはやはり再帰を使う.たとえば、次の木です.
　　　　　　　　　　　　1
　　　　　　　　　　  /   \
　　　　　　　　　　 2        3
    　　　　　　　　/   \   /   \
　　　　　　　　　4     5  6     7
この木の場合、最大パスは5->2->1->3->7です.
では、この経路はどのように求められたのでしょうか.ここではグローバル変数Solutionを使用する必要がある.maxは、いつでもより大きなパスと置き換えられます.関数が左サブツリーに再帰された場合、最大パスは4->2->5です.ただし、この場合の関数の戻り値は、4->2と5->2の2つのパスの中で最大の1つである必要があります.右の木は同じです.そしてSolution.maxは、各サブツリーの最大パスとを監視するために使用されます.(左サブツリーの最大パスと、右サブツリーの最大パスと、左サブツリーのroot.leftを起点とする最大パス(ゼロより大きい必要がある)+右サブツリーのroot.rightは起点の最大経路(ゼロより大きい必要がある)+root.val)、この3つの最大値は最大のパスとです.
コード:

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

class Solution:
    # @param root, a tree node
    # @return an integer
    def maxsum(self, root):
        if root == None: return 0
        sum = root.val
        lmax = 0; rmax = 0
        if root.left:
            lmax = self.maxsum(root.left)
            if lmax > 0:
                sum += lmax
        if root.right:
            rmax = self.maxsum(root.right)
            if rmax > 0:
                sum += rmax
        if sum > Solution.max: Solution.max = sum
        return max(root.val, max(root.val + lmax, root.val + rmax))
    
    def maxPathSum(self, root):
        Solution.max = -10000000
        if root == None: return 0
        self.maxsum(root)
        return Solution.max