二叉树中的最大路径和

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

解题思路：

有4种情况要考虑 left + root

right + root

root

left + right + root

不断往上传递的值 只可能是 1， 2， 3中的一种 第四种情况只可能保存在 max里面 而不可能在 curr_max

参考横向纵向，向上生长的只能是一个单支，横向的是总体结果。所以对于某个node,纵向更新单支并返回，横向更新结果。

递归

首先，考虑实现一个简化的函数 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的最大半枝



```