Longest Substring Without Repeating Characters (Python)
Candy (Python)

Binary Tree Maximum Path Sum (Python)

kitt posted @ 2014年2月11日 21:12 in LeetCode , 2773 阅读

每个node的值可正可负, 参考了网上C++解法, 类变量Solution.maxSum用于记录最大路径和, 当level为0时返回它; maxPathSum(root)函数返回的是经过root的路径最大和, 可以只是root, 也可以是左子树某一部分+root或者root+右子树某一部分。这个函数是可以返回0的, 也就是说currRoot, currRoot+左子树, currRoot+右子树的值都小于等于0, 对max path sum没有贡献, 之后就不再考虑了。

# 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
    deep = 0

    def maxPathSum(self, root):
        if root == None:
            return 0
        if Solution.deep == 0: # Solution.maxSum is set to infinitesimal every time when a new test case starts
            Solution.maxSum = -10 ** 10
        Solution.deep += 1
        vLeft = self.maxPathSum(root.left)
        vRight = self.maxPathSum(root.right)
        Solution.deep -= 1
        Solution.maxSum = max(root.val + vLeft + vRight, Solution.maxSum)
        if Solution.deep == 0:
            return Solution.maxSum
        return max(root.val + vLeft, root.val + vRight, 0)
Avatar_small
yzl232 说:
2014年9月15日 13:03

可以稍作优化。

class Solution:
    # @param root, a tree node
    # @return an integer
    def maxPathSum(self, root):
        self.maxSum = -10**10
        self.dfs(root)
        return self.maxSum

    def dfs(self, root):
        if not root: return 0
        vLeft = self.dfs(root.left)
        vRight = self.dfs(root.right)
        self.maxSum = max(self.maxSum, vLeft+vRight+root.val)
        return max(root.val+vLeft, root.val+vRight, 0)

Avatar_small
kitt 说:
2015年3月04日 05:10

很简洁很强大! thx~ @yzl232:


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter