Description:
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Examples:
Example 1:
Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.Solution in Python:
To solve the problem of finding the maximum path sum in a binary tree, we need to implement a solution that considers all possible paths in the tree. Here’s a step-by-step approach to solve this problem:
- Define the TreeNode class: Ensure we have a class definition for the nodes of the binary tree.
- Recursive Function to Calculate Path Sums: We need a helper function that computes the maximum path sum that can be obtained including the current node and extending to one of its children.
- Global Variable for Maximum Path Sum: We use a global variable to keep track of the maximum path sum encountered during the recursion.
- Recursive Calculation: For each node, compute the maximum path sum passing through the node and its left or right child, and update the global maximum if the sum through the current node (including both children) is higher.
Python
# 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:
# Initialize a variable to store the maximum path sum
self.max_sum = float('-inf')
def max_gain(node):
"""
Helper function to compute the maximum path sum with the highest
gain starting from the given node.
"""
if not node:
return 0
# Recursively calculate the maximum path sum for left and right subtrees
# Only add positive gains to avoid reducing the overall path sum
left_gain = max(max_gain(node.left), 0)
right_gain = max(max_gain(node.right), 0)
# Calculate the path sum that passes through the current node
current_max_path = node.val + left_gain + right_gain
# Update the global maximum path sum if the current path is better
self.max_sum = max(self.max_sum, current_max_path)
# Return the maximum gain that can be obtained by including the current node
# and extending to either the left or right subtree
return node.val + max(left_gain, right_gain)
# Start the recursion from the root node
max_gain(root)
return self.max_sumExplanation
- TreeNode Class Definition: This is the standard definition for a tree node in Python.
- maxPathSum Function: This is the main function that initializes the
max_sumvariable and starts the recursive calculation usingmax_gain. - max_gain Function:
- For each node, calculate the maximum gain from its left and right subtrees.
- Ensure we only consider positive gains (
max(..., 0)) to avoid reducing the overall sum. - Calculate the path sum that includes the current node and its maximum gains from both children.
- Update the
max_sumif the current path sum is greater. - Return the maximum gain that can be used by the parent node.
Constraints Handling
- The solution handles trees with negative values by ensuring that we consider the maximum of subtree sums and zero (
max(left_gain, 0)) which effectively ignores negative paths. - The recursion ensures that all paths are considered, including those not passing through the root, and keeps track of the maximum path sum globally.
This approach ensures that we efficiently compute the maximum path sum in the binary tree with a time complexity of O(n), where n is the number of nodes in the tree.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
// Initialize a variable to store the maximum path sum
let maxSum = -Infinity;
/**
* Helper function to compute the maximum path sum with the highest
* gain starting from the given node.
* @param {TreeNode} node
* @return {number}
*/
function maxGain(node) {
if (node === null) {
return 0;
}
// Recursively calculate the maximum path sum for left and right subtrees
// Only add positive gains to avoid reducing the overall path sum
let leftGain = Math.max(maxGain(node.left), 0);
let rightGain = Math.max(maxGain(node.right), 0);
// Calculate the path sum that passes through the current node
let currentMaxPath = node.val + leftGain + rightGain;
// Update the global maximum path sum if the current path is better
maxSum = Math.max(maxSum, currentMaxPath);
// Return the maximum gain that can be obtained by including the current node
// and extending to either the left or right subtree
return node.val + Math.max(leftGain, rightGain);
}
// Start the recursion from the root node
maxGain(root);
return maxSum;
};Solution in Java:
Java
class Solution {
// Global variable to store the maximum path sum
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
// Call the recursive function to calculate the maximum path sum starting from the root
maxGain(root);
return maxSum;
}
private int maxGain(TreeNode node) {
// Base case: if node is null, return 0 (no gain from null node)
if (node == null) {
return 0;
}
// Recursively calculate the maximum gain from left and right subtrees
// Ensure to only add positive gains to avoid reducing the overall path sum
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// Calculate the path sum that passes through the current node
int currentMaxPath = node.val + leftGain + rightGain;
// Update the global maximum path sum if the current path is better
maxSum = Math.max(maxSum, currentMaxPath);
// Return the maximum gain that can be obtained by including the current node
// and extending to either the left or right subtree
return node.val + Math.max(leftGain, rightGain);
}
}Solution in C#:
C#
public class Solution {
// Global variable to store the maximum path sum
private int maxSum = int.MinValue;
public int MaxPathSum(TreeNode root) {
// Call the recursive function to calculate the maximum path sum starting from the root
MaxGain(root);
return maxSum;
}
private int MaxGain(TreeNode node) {
// Base case: if node is null, return 0 (no gain from null node)
if (node == null) {
return 0;
}
// Recursively calculate the maximum gain from left and right subtrees
// Ensure to only add positive gains to avoid reducing the overall path sum
int leftGain = Math.Max(MaxGain(node.left), 0);
int rightGain = Math.Max(MaxGain(node.right), 0);
// Calculate the path sum that passes through the current node
int currentMaxPath = node.val + leftGain + rightGain;
// Update the global maximum path sum if the current path is better
maxSum = Math.Max(maxSum, currentMaxPath);
// Return the maximum gain that can be obtained by including the current node
// and extending to either the left or right subtree
return node.val + Math.Max(leftGain, rightGain);
}
}