Binary Tree Maximum Path Sum, Hard Leetcode Problem
Problem is here: https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
This is in essence a variation of the Largest Binary Search Tree problem previously discussed. The idea will be to do it in linear time via post-search traversal: at every node, compute the max sum ending at that node and thru that node. Once you do it for all trees in the left, and all trees in the right, the calculation for the current node becomes relatively simple. Note that for both the at as well as the thru calculation, you only use the information stored at the at variable. The thru is only used when calculating the max total. Code is below, cheers, Marcelo.
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 1:
Input: [1,2,3] 1 / \ 2 3 Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42
This is in essence a variation of the Largest Binary Search Tree problem previously discussed. The idea will be to do it in linear time via post-search traversal: at every node, compute the max sum ending at that node and thru that node. Once you do it for all trees in the left, and all trees in the right, the calculation for the current node becomes relatively simple. Note that for both the at as well as the thru calculation, you only use the information stored at the at variable. The thru is only used when calculating the max total. Code is below, cheers, Marcelo.
public class Solution
{
public int MaxPathSum(TreeNode root)
{
if (root == null) return 0;
int maxAt = 0;
int maxThru = 0;
int maxTotal = Int32.MinValue;
MaxPathSum(root, ref maxAt, ref maxThru, ref maxTotal);
return maxTotal;
}
private void MaxPathSum(TreeNode root,
ref int maxAt,
ref int maxThru,
ref int maxTotal)
{
if (root == null) return;
int maxAtLeft = 0;
int maxThruLeft = 0;
MaxPathSum(root.left, ref maxAtLeft, ref maxThruLeft, ref maxTotal);
int maxAtRight = 0;
int maxThruRight = 0;
MaxPathSum(root.right, ref maxAtRight, ref maxThruRight, ref maxTotal);
maxThru = root.val;
maxThru = Math.Max(maxThru, root.val + maxAtLeft + maxAtRight);
maxThru = Math.Max(maxThru, root.val + maxAtLeft);
maxThru = Math.Max(maxThru, root.val + maxAtRight);
maxAt = root.val;
maxAt = Math.Max(maxAt, root.val + maxAtLeft);
maxAt = Math.Max(maxAt, root.val + maxAtRight);
maxTotal = Math.Max(maxTotal, maxAt);
maxTotal = Math.Max(maxTotal, maxThru);
}
}
This is super concise! I'm not a huge fan of ref parameters, but overall I think I like how concise your solution is more than mine, even though Python helps with conciseness:
ReplyDeleteclass Solution:
def safeMax(self, x, y):
if not x:
return y
if not y:
return x
return max(x, y)
def maxPathSumHelper(self, root):
if not root:
return None, None
max_in_left, max_starting_at_left = self.maxPathSumHelper(root.left)
max_in_right, max_starting_at_right = self.maxPathSumHelper(root.right)
max_path_starting_at_child = self.safeMax(max_starting_at_left, max_starting_at_right)
path_starting_here = root.val
if max_path_starting_at_child is not None and max_path_starting_at_child > 0:
path_starting_here += max_path_starting_at_child
path_through_here = root.val
if max_starting_at_left is not None and max_starting_at_left > 0:
path_through_here += max_starting_at_left
if max_starting_at_right is not None and max_starting_at_right > 0:
path_through_here += max_starting_at_right
max_path_sum = path_through_here
max_in_child = self.safeMax(max_in_left, max_in_right)
if max_in_child is not None:
max_path_sum = max(max_path_sum, max_in_child)
return max_path_sum, path_starting_here
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return self.maxPathSumHelper(root)[0]
Cheers,
Taras