💬 Discord
Sign In
NeetCode #473LC-124HardTreesBlind 75NC 150NC 250
← Back to All Problems

#473 · #124 · Binary Tree Maximum Path Sum(二叉树中的最大路径和)

📌 Problem Statement & Constraints

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes is connected by an edge; a node may appear at most once. Given the root, return the maximum path sum of any non-empty path. Constraints: the number of nodes is in [1, 3 * 10^4], -1000 <= Node.val <= 1000.

💡 Core Algorithmic Approaches

  1. For each node, the best downward path through it is node.val + max(left_gain, right_gain, 0) -- a negative branch is simply not taken.
  2. The best path bending at the node is node.val + max(left_gain, 0) + max(right_gain, 0), which is a candidate answer.
  3. The recursion returns the downward gain while updating a global maximum with the bending value.
  4. The max(..., 0) clamps are essential: they let the algorithm discard negative subtrees.

💻 Benchmark Python3 Implementation

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.best = float("-inf")

        def gain(node: Optional[TreeNode]) -> int:
            """Maximum sum of a downward path starting at this node (>= 0)."""
            if not node:
                return 0
            l = max(gain(node.left), 0)    # discard negative branches
            r = max(gain(node.right), 0)
            # a path bending at this node is a candidate answer
            self.best = max(self.best, node.val + l + r)
            # only one branch may be extended upward
            return node.val + max(l, r)

        gain(root)
        return self.best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one post-order traversal.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Returning node.val + l + r from the recursion: a path cannot use both branches when extended upward; the return value must use only one.
  • Forgetting the max(..., 0) clamps: negative branches would reduce the sum, so they must be discarded.
  • Initialising best to 0: all values can be negative, so the answer may be negative; -infinity is required.
  • Not considering a single node as a path: the bending candidate at a leaf is exactly node.val, which covers it.