# \[124]\[困难]\[DFS] 二叉树中的最大路径和

## 题目描述

[124. 二叉树中的最大路径和](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1：

```
输入：[1,2,3]

       1
      / \
     2   3

输出：6
```

示例 2：

```
输入：[-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出：42
```

## 解题思路

本题的关键在于理解题目所说的路径. 路径首先是着眼于某一个节点(对应题目中`路径被定义为一条从树中任意节点出发`), 然后对于左右子树, 从中各找到一条**普通意义的路径**, 即从这个结点开始, 向下连接, 形成一条**可以有曲折但不能有分叉的连线**, 可以在任何一个位置停止.

因此本体中的路径, 只能在开始的节点处分叉, 可以由左右两条连线组成, 也可以只有一条, 或仅仅只有一个节点组成.

如其他的路径问题一样, 使用DFS解决问题. 对于每个节点, 计算这个节点所有可能路径的最大值, 需要考虑节点值, 左右子树的**连线**, 判断左右子树递归返回的连线最大值是否大于0, 大于0则可以包含这条路径, 否则抛弃. 计算得到这个节点的最大路径之后, 与全局的进行比较, 保存更大的值.

在计算节点路径值的时候, 要求左右子树返回的是**最长连线值**, 而**不是最长路径**, 因为对于当前节点, 在左右子树中不能再有分叉, 只能使用连线. 因此DFS递归函数, 返回的是连线值. 连线值就考虑的是节点本身, 以及左右子树中连线的较大值, 如果这个较大值大于0, 需要与节点本身组成更长的连线, 一起返回, 否则, 只返回节点本身的值即可.

```python
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def max_gain(node):
            nonlocal max_sum
            if not node:
                return 0

            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)

            price_newpath = node.val + left_gain + right_gain
            max_sum = max(max_sum, price_newpath)

            return node.val + max(left_gain, right_gain)

        max_sum = float('-inf')
        max_gain(root)
        return max_sum
```