Leetcode 124 Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum"/>

Leetcode 124 Binary Tree Maximum Path Sum

**Leetcode 124 Binary Tree Maximum Path Sum

题目描述

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]1/ \2   3
Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]-10/ \9  20/  \15   7
Output: 42   

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路解析

这里的最大路径和实质上指的是路径上结点权值之和，路径上相邻两个结点具备父子关系即可，顺序可以是子父，也可以是父子。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:max_sum = float('-inf') # 记录最大路径和def maxPathSum(self, root: TreeNode) -> int:self.max_path_sum(root)return self.max_sum# max_path_sum的返回值只表示以根节点的子结点为根节点的树的最大路径和，对于根节点，他的返回值实际上没有作用def max_path_sum(self, root):if not root:return 0left_sum = max(self.max_path_sum(root.left), 0)right_sum = max(self.max_path_sum(root.right), 0)new_path = root.val + left_sum + right_sumself.max_sum = max(self.max_sum, new_path)return root.val + max(left_sum, right_sum)  # 对于当前结点，路径中只能选择左子树和右子树中的一个