LeetCodeブラシ|Binary Tree Maximum Path Sum

タイトルリンク:https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
心得:
それほど難しくない問題だと思っていたのに、久しぶりにやりました==.
全体的な考え方は再帰的であり、findMax(self,root,maxPath)関数はrootノードを終点とする最も大きなサブパスを返すために使用され、maxPathでは既存の最小maxPathSum値が常に維持されている.
MACコードは以下の通りである.

# --*-- coding:utf-8 --*--
# 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 maxPathSum(self, root):
        if root == None:
            return 0
        maxPath = [root.val]
        self.findMax(root, maxPath) #    root       
        return maxPath[0]
    def findMax(self, root, maxPath):
        if root == None:
            return 0
        lMax = self.findMax(root.left, maxPath)
        rMax = self.findMax(root.right, maxPath)
        result = max(root.val, lMax + root.val, rMax + root.val)
        maxPath[0] = max(result, maxPath[0], lMax + rMax + root.val)
        return result

if __name__ == "__main__":
    r = TreeNode(0)
    s = Solution()
    print s.maxPathSum(r)
    #data = [5,4,8,11,None,13,4,7,2,None,None,None,1]