题目描述
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
解题思路
递归。维护一个变量用来保存最大的路径和，对于每个节点，都有两个值：max_gain 和 cur_sum，分别用来存储当前节点的最大收益（连接到子节点是否能取得更大的收益）、包含当前节点的更低层的路径的最大和（该数与最大路径和相比较更新）。边界条件：None 节点的 max_gain 为 0。
代码
Python 3.61
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.max_sum = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def max_gain(node):
if node is None:
return 0
left_gain = max(max_gain(node.left), 0)
right_gain = max(max_gain(node.right), 0)
cur_sum = node.val + left_gain + right_gain
self.max_sum = max(cur_sum, self.max_sum)
return node.val + max(left_gain, right_gain)
max_gain(root)
return self.max_sum执行用时：128 ms内存消耗：22.2 MB