LeetCode 124. 二叉树中的最大路径和

124. 二叉树中的最大路径和

Difficulty: 困难

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1：

输入：[1,2,3]

       1
      / 
     2   3

输出：6

示例 2：

输入：[-10,9,20,null,null,15,7]

   -10
   / 
  9  20
    /  
   15   7

输出：42

Solution

Language: 全部题目

题目读起来有点拗口，简单的理解是在整棵树中找到连接两个节点的一条路径，并且路径上的节点和是所有可能路径中最大的。

需要考虑节点的值全部为负数的情况，此时不能直接返回0。可以考虑每个节点的左右两颗子树，求子树的最大路径和，然后返回root.val + max(l, r)。

参考：花花酱 LeetCode 124. Binary Tree Maximum Path Sum - 刷题找工作 EP90 - YouTube

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.res = -float("inf")
        self.helper(root)
        return self.res
        
    def helper(self, root):
        if not root: return 0
        l = max(0, self.helper(root.left))
        r = max(0, self.helper(root.right))
        self.res = max(self.res, root.val + l + r)
        return root.val + max(l, r)