124. Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/
solution
首先计算单个节点的最大路径 val + max(l, r)
但只能发生一次,整体路径最大:max(res, l + r + root.val)
在1的计算过程中,找到2最大的
class Solution:
def __init__(self):
self.res = float('-inf')
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.dfs(root)
return self.res
def dfs(self, root):
if root is None:
return 0
l = self.dfs(root.left)
r = self.dfs(root.right)
self.res = max(self.res, l + r + root.val)
return max(root.val + max(l, r), 0)
时间复杂度:O(n) 空间复杂度:O(h)
follow up
*298. Binary Tree Longest Consecutive Sequence
class Solution:
def __init__(self):
self.res = 0
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
self.dfs(root)
return self.res
def dfs(self, root):
if not root:
return 0
l = self.dfs(root.left) + 1
r = self.dfs(root.right) + 1
if root.left and root.left.val - root.val != 1:
l = 1
if root.right and root.right.val - root.val != 1:
r = 1
self.res = max(self.res, max(l, r))
return max(l, r)
*1120. Maximum Average Subtree
*1973. Count Nodes Equal to Sum of Descendants
Last updated