描述

給出一棵二叉樹，尋找一條路徑使其路徑和最大，路徑可以在任一節(jié)點中開始和結束（路徑和為兩個節(jié)點之間所在路徑上的節(jié)點權值之和）

樣例

給出一棵二叉樹：

   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)

仔細想，發(fā)現(xiàn)從任意節(jié)點開始和結束，其實就意味最大路徑和可以選擇子樹的根節(jié)點作為計算路徑和的開始，則

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

就表達出了最大路徑可以是任意子樹的經過根節(jié)點的最大路徑和。