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