二叉树中的最大路径和

https://www.lintcode.com/problem/94/?utm_source=sc-cheatsheet-cyc

描述

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

关于树的表示

样例

样例 1：

输入：

tree = {2}

输出：

2

解释：

只有一个节点2 样例 2：

输入：

tree = {1,2,3}

输出：

6

解释：

如下图，最长路径为2-1-3      1     / \    2   3

样例 3： 输入：

tree = {1, 2, 3, 4, 9, 6, #, 1, 3, 4, #, 8, 12, #, 14, #, 3, 6}

输出：

43

解释：

如下图，最长路径为 14-1-4-2-1-3-6-12

94_1.png

解题思路：

递归

首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体而言，该函数的计算如下。

• 空节点的最大贡献值等于 $00$。

• 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。

• 根据函数 maxGain 得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。

```python
from lintcode import (
    TreeNode,
)

"""
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 max_path_sum(self, root: TreeNode) -> int:
        # write your code here
        if not root:
            return 0
        self.maxSum = float('-inf')
        self.helper(root)
        return self.maxSum

    def helper(self, root: TreeNode) -> int: #得到含当前root的最大半枝
        if not root:
            return 0
        l = max(self.helper(root.left), 0) #左右半枝是否需要包含
        r = max(self.helper(root.right),0)
        self.maxSum = max(self.maxSum, l + root.val + r)#当前路线（含root）和已知路径相比，全条非半枝
        return max(root.val + l, root.val + r)#含root的最大半枝



```