LeetCode: 124 Binary Tree Maximum Path Sum

Problem Statement

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:

Input: [1,2,3]
       1
      / \
     2   3
Output: 6

Input: [-10,9,20,null,null,15,7]
   -10
   /  \
  9   20
     /  \
    15   7
Output: 42

问题

给定一个非空二叉树，找到路径和最大的路径。对于这个问题，路径被定义为从某个起始节点到树中任何节点的任意节点序列，沿父子连接。路径必须包含至少一个节点，并且不需要经过根节点。

解决方案 1

使用递归来计算每个节点的最大贡献值，并使用全局变量来记录最大路径和。

Approach 1 / 方法 1

通过递归遍历每个节点，计算从当前节点出发的最大路径和。同时，更新全局的最大路径和。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Initialize a global variable to store the maximum path sum.
   初始化一个全局变量来存储最大路径和。

Step 1 / 第一步:

2. Define a helper function to calculate the maximum path sum starting from the current node.
   定义一个辅助函数来计算从当前节点开始的最大路径和。

Step 2 / 第二步:

3. For each node, calculate the maximum path sum of the left and right subtrees.
   对于每个节点，计算左右子树的最大路径和。

Step 3 / 第三步:

4. Update the global maximum path sum with the maximum value between the current path sum and the existing maximum path sum.
   使用当前路径和与现有最大路径和之间的最大值更新全局最大路径和。

Implementation / 实现

python

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.max_sum = float('-inf')

        def max_gain(node):
            if not node:
                return 0
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            price_newpath = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, price_newpath)
            return node.val + max(left_gain, right_gain)

        max_gain(root)
        return self.max_sum

Explanation / 解释

1. Step 1 / 第一步:

• The helper function max_gain returns the maximum path sum including the current node.
  辅助函数 max_gain 返回包含当前节点的最大路径和。

2. Step 2 / 第二步:

• For each node, calculate the left and right gains. If the gain is negative, discard it by taking max(0, gain).
  对于每个节点，计算左右增益。如果增益为负，通过取 max(0, gain) 来舍弃它。

3. Step 3 / 第三步:

• Update the global max_sum with the maximum value between the current path sum and the existing maximum path sum.
  用当前路径和与现有最大路径和之间的最大值更新全局 max_sum。

Complexity Analysis / 复杂度分析

• Time Complexity: O(N), where N is the number of nodes in the tree.
  时间复杂度: O(N)，其中 N 是树中的节点数。

• Space Complexity: O(H), where H is the height of the tree.
  空间复杂度: O(H)，其中 H 是树的高度。

Key Concept / 关键概念

• The key concept is to use a recursive approach to calculate the maximum path sum for each node, and keep track of the global maximum path sum.
  关键概念是使用递归方法计算每个节点的最大路径和，并跟踪全局最大路径和。

解决方案 2

使用类似的递归方法，但在计算过程中加入更多的细节来优化性能。

Approach 2 / 方法 2

通过优化递归计算过程，减少不必要的计算和存储。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Initialize the global variable to store the maximum path sum.
   初始化全局变量来存储最大路径和。

Step 1 / 第一步:

2. Define the recursive function to calculate the maximum gain from each node.
   定义递归函数来计算每个节点的最大增益。

Step 2 / 第二步:

3. Calculate the left and right gains for each node.
   计算每个节点的左右增益。

Step 3 / 第三步:

4. Update the maximum path sum if the current path sum is greater.
   如果当前路径和较大，则更新最大路径和。

Implementation / 实现

python

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def helper(node):
            nonlocal max_sum
            if not node:
                return 0
            left_max = max(helper(node.left), 0)
            right_max = max(helper(node.right), 0)
            local_max = node.val + left_max + right_max
            max_sum = max(max_sum, local_max)
            return node.val + max(left_max, right_max)

        max_sum = float('-inf')
        helper(root)
        return max_sum

Explanation / 解释

1. Step 1 / 第一步:

• Use a nested helper function to calculate the maximum gain.
  使用嵌套的辅助函数计算最大增益。

2. Step 2 / 第二步:

• For each node, calculate the left and right maximum gains.
  对于每个节点，计算左右最大增益。

3. Step 3 / 第三步:

• Update the global maximum path sum if the current path sum is greater.
  如果当前路径和较大，则更新全局最大路径和。

Complexity Analysis / 复杂度分析

• Time Complexity: O(N)
  时间复杂度: O(N)

• Space Complexity: O(H)
  空间复杂度: O(H)

Key Concept / 关键概念

• The key concept is similar to the first approach, with an emphasis on optimizing the recursive calculation.
  关键概念与第一种方法类似，重点是优化递归计算。

Tips / 提示

• Remember to consider the case where the tree has only one node.
  记得考虑树只有一个节点的情况。

Solution Template for similar questions / 提示

• The general approach can be applied to other problems involving tree traversal and path sum calculations.
  通用方法可以应用于其他涉及树遍历和路径和计算的问题。

Recommended 5 more similar questions / 推荐5问题

1. LeetCode 543: Diameter of Binary Tree
2. LeetCode 112: Path Sum
3. LeetCode 113: Path Sum II
4. LeetCode 437: Path Sum III
5. LeetCode 687: Longest Univalue Path

More.

• LeetCode Explore – Binary Tree
• GeeksforGeeks – Binary Tree Data Structure
• InterviewBit – Binary Tree Interview Questions

• 20天学 Algorithm – Tree

by NeetCode

by AlgosWithMichael