LintCode-二叉树中的最大路径和

描述

给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）

样例

给出一棵二叉树：

   1
  / \
 2   3

返回 6

代码

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of binary tree.
    @return: An integer
    """
    def maxPathSum(self, root):
        # write your code here
        self.maxPath = root.val
        self.Dfs(root)
        return self.maxPath
    
    def Dfs(self, root):
        # TODO: write code...
        if root is None:
            return 0
        left = max(0, self.Dfs(root.left))
        right = max(0, self.Dfs(root.right))
        leap = left + root.val + right
        if leap > self.maxPath:
            self.maxPath = leap
        return max(left + root.val, right + root.val)

仔细想，发现从任意节点开始和结束，其实就意味最大路径和可以选择子树的根节点作为计算路径和的开始，则

leap = left + root.val + right
        if leap > self.maxPath:
            self.maxPath = leap

就表达出了最大路径可以是任意子树的经过根节点的最大路径和。