题目

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

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

示例 1:
输入:** [1,2,3]

  1.    **1**<br />      **/ \**<br />     **2**   **3**

输出: 6

示例 2:
输入: [-10,9,20,null,null,15,7]

-10
/ \
9 20
/ \
15 7

输出: 42

方案一（递归）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        ans = float('-inf') # 最大路径和
        def helper(node):
            nonlocal ans
            if not node:
                return 0

            # 左右子树最大路径和
            left = max(0, helper(node.left))
            right = max(0, helper(node.right))

            # 经过该节点的最大路径和
            ans = max(ans, node.val + left + right)

            # 经过当前节点的最大路径和
            return node.val + max(left, right)

        helper(root)
        return ans

原文

https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/285/tree/1275/
https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-ikaruga/
https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-de-zui-da-lu-jing-he-by-leetcode/