Description
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Solution
分治法。
需要考虑的是,子树中最大的路不一定必过根节点。所以要记录single Path的值。
计算树的最长path有2种情况:
- 通过根的path.
(1)如果左子树从左树根到任何一个Node的path大于零,可以链到root上
(2)如果右子树从右树根到任何一个Node的path大于零,可以链到root上
- 不通过根的path. 这个可以取左子树及右子树的path的最大值。
所以创建一个inner class:
记录2个值:
-
本树的最大path。
-
本树从根节点出发到任何一个节点的最大path.
当root == null,以上2个值都要置为Integer_MIN_VALUE; 因为没有节点可取的时候,是不存在solution的。以免干扰递归的计算
# 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:
maxSum, _ = self.maxPathHelper(root)
return maxSum
def maxPathHelper(self, root):
if root is None:
return -float("inf"), 0
left = self.maxPathHelper(root.left)
right = self.maxPathHelper(root.right)
maxpath = max(left[0], right[0], root.val + left[1] + right[1])
single = max(left[1] + root.val, right[1] + root.val,0)
return maxpath, single
网友评论