【Leetcode】【python】Binary Tree Maximum Path Sum 二叉树中的最大路径和

题目大意

求一棵二叉树中最大的路径和。该路径可以是二叉树中某一节点到树中任意一个节点的所经过的路径，不允许重复经过一个节点，不必经过根节点。

解题思路

参考：

https://shenjie1993.gitbooks.io/leetcode-python/124%20Binary%20Tree%20Maximum%20Path%20Sum.html
我们现在要求最大路径和，那么就要分别得到左右两条路径的最大和。而左路径的最大和为左节点的值加上它左右路径中较大的路径和，右路径最大和为右节点的值加上它左右路径中较大的路径和。
注意：如果某条子路径的左右节点为负，直接置为0，等于不走这个节点。

代码

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxSum = float('-inf')
        self._maxPathSum(root)
        return self.maxSum

    def _maxPathSum(self, root):  # DFS
        if root is None:
            return 0
        left = self._maxPathSum(root.left)
        right = self._maxPathSum(root.right)
        left = left if left > 0 else 0
        right = right if right > 0 else 0
        self.maxSum = max(self.maxSum, root.val + left + right)
        # print self.maxSum
        return max(left, right) + root.val

总结

难在思路，代码还是比较容易理解。