Thursday, September 18, 2014

Leetcode: Binary Tree Maximum Path Sum @Python

# 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
    pathsum=-2**31
    def sumpath(self,root):
        subsum=-2**31
        if not root: 
            return 0
        else:
            lsum=self.sumpath(root.left)
            rsum=self.sumpath(root.right)
            subsum=max(lsum+root.val,rsum+root.val,root.val)
            self.pathsum=max(subsum,lsum+rsum+root.val,self.pathsum)
            return subsum
    def maxPathSum(self, root):
        if not root: return None
        self.sumpath(root)
        return self.pathsum

No comments :

Post a Comment