Binary Tree Maximum Path Sum
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge, and each node appears at most once. The path does not need to pass through the root. The path sum is the sum of the node values on it.
Given the root, return the maximum path sum of any non-empty path.
Constraints:
- The number of nodes is in the range
[1, 3 * 10^4]. -1000 <= Node.val <= 1000
Intuition
This is the diameter problem with sums instead of lengths, plus one twist: values can be negative.
Every path has a highest node where it turns. For that node, the best path through it is:
node value + best downward gain from the left + best downward gain from the right
A downward gain from a child is the best sum of a chain that starts at that child and goes down. If that gain is negative, we are better off not taking it, so we use max(0, gain).
Approach: DFS Returning the Best Downward Chain
Keep a global best, initialized to a very small number (not 0, because the answer can be negative).
- If the node is
null, return 0. left = max(0, gain(node.left))andright = max(0, gain(node.right)).- Update
best = max(best, node.val + left + right). This is the best path that turns at this node. - Return
node.val + max(left, right)to the parent. The parent can only extend one side, because a path cannot branch.
The key rule is the same as in diameter: the return value is a single chain, the updated answer uses both sides.
Code
class Solution {int best;int gain(TreeNode* node) {if (node == nullptr) return 0;int left = max(0, gain(node->left));int right = max(0, gain(node->right));best = max(best, node->val + left + right);return node->val + max(left, right);}public:int maxPathSum(TreeNode* root) {best = INT_MIN;gain(root);return best;}};
Complexity
Each node is visited exactly once.
Recursion stack depth equals the tree height.