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) # 对于当前结点,路径中只能选择左子树和右子树中的一个
更多推荐
Leetcode 124 Binary Tree Maximum Path Sum
发布评论