# 二叉树中的最大路径和

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E5%9B%B0%E9%9A%BE\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#困难) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E4%BA%8C%E5%8F%89%E6%A0%91/%E6%A0%91\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#二叉树树)

**问题简述**

```
求给定二叉树中的最大路径和。
路径定义：
    1. 同一个节点在路径中最多出现一次；
    2. 路径至少包含一个节点，可以不经过根节点；
```

> [二叉树中的最大路径和\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a)

**思路：DFS**

* 定义函数 `maxGain(node)` 表示以 `node` 为**起点**的最大路径；显然 maxGain 可以通过递归计算（详见代码）；
* 则**经过** `node` 的最大路径和，可以表示为 `node.val + maxGain(node.left), maxGain(node.right)`；因此可以在计算 `maxGain(root)` 的过程中，记录经过每个节点的最大路径和，进而得到全局最大路径。

<details>

<summary><strong>Python</strong></summary>

```python
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        # write code here

        self.ret = float('-inf')

        def maxGain(node):
            if not node: return 0

            # 如果子路径的 maxGain 为负数，那么对 node 来说 maxGain 就是自己本身；
            max_left = max(0, maxGain(node.left))
            max_right = max(0, maxGain(node.right))
            # 记录“经过”node 节点的最大路径
            self.ret = max(self.ret, node.val + max_left + max_right)
            return node.val + max(max_left, max_right)  # 至少要包含自己本身

        maxGain(root)
        return self.ret
```

</details>