LC 0124 [H] Binary Tree Maximum Path Sum - ALawliet/algorithms GitHub Wiki
just like finding diameter but the most important trick is handling the negatives. if a branch has negative, we don't want to explore it because we are only interested in exploring a path if it gives us gains. for example [2,-1]. we would just stay at 2 + 0 = 2 instead of going left for 2 - 1 = 1.
2 = 0L + 0R + 2x
0 + 2x
3 = 0L + 0R + 3x
0 + 3x
6 = 2L + 3R + 1x
3 + 1x
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.global_sum = -math.inf
def postorder(x):
if not x: return 0
# post-order: we need to explore the branches before we can evaluate the root
L = max(postorder(x.left), 0)
R = max(postorder(x.right), 0)
local_sum = L + R + x.val #
# print(f'{local_sum} = {L}L + {R}R + {x.val}x')
self.global_sum = max(self.global_sum, local_sum)
# continue exploring the bigger branch
# if negative, then just stay put and take the 0
# print(f'{max(L, R)} + {x.val}x')
return max(L, R) + x.val #
postorder(root)
return self.global_sum
post-order traversal
- we want to pay attention to gains, and less than 0 isn't worth it, so if you had a -n gain vs. 0, you'd take 0 and try to disregard the -n path
- the local node value = gain on the left + current value + gain on the right #
- we check these local sums against the global max bag
- but from the child, we pass up to the parent only the current value + max of the gain on either the left or the right - this is all the parent cares about to get the final answer #
This problem isn't particularly well defined. In this case, from each node there are 3 possible path - the root itself, a path via left tree, a path via right tree, and the max sum is the max from these 4 cases (root, root+left, root+right, root+left+right), as you can ignore the negative paths. It doesn't mean all possible path.
maxValue is the value which recording whether this current root is the final root, so we use left + right + node.val. But to the upper layer(after return statement), we cannot choose both left and right brunches, so we need to select the larger one, so we use max(left, right) + node.val to prune the lower brunch.
In the end, very elegant solution, thank you for your sharing!
I think it means only the final root can add up both left and right (and it can choose if would like to add left/right, since it's comparing left/right value with 0). For any other node, it has to choose either go left or go right, or neither, otherwise there would be a small tree, not a single line.
As the host said 'Once it goes down, it can't go up.'
When root calls maxPathDown(root.left), it wants it to return the maxSum from root.left's left branch or right branch, not both.
If both, then the route would be root.left's left branch -> root.left -> root.left's right branch (direction: up -> down), when it arrives the root.left's right branch, it can no longer go back to root.left in order to go back to root.
Each node actually has two roles when it comes to function maxPathDown. When processing the final result maxValue, the node is treated as the highest point of a path. When calculating its return value, it is only part of a path (left or right part), and this return value will be used to calculate path sum of other paths with some other nodes(above the current one) as their highest point.
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
def max_gain(node):
if not node: return 0
# post-order traversal
L_gain = max(max_gain(node.left), 0)
R_gain = max(max_gain(node.right), 0)
# sum AT current node to check against the global max
local_sum = node.val + L_gain + R_gain #
self.global_sum = max(self.global_sum, local_sum)
# sum FROM current node to pass onto next
next_sum = node.val + max(L_gain, R_gain) #
return next_sum
self.global_sum = -math.inf
max_gain(root)
return self.global_sum
just like finding Diameter except max(_, 0) and + node.val instead of + 1
class MaximumPathSum:
def find_maximum_path_sum(self, root):
self.global_max = -math.inf
self.find_maximum_path_sum_recursive(root)
return self.global_max
def find_maximum_path_sum_recursive(self, node):
if node is None: return 0
L_max = max(self.find_maximum_path_sum_recursive(node.left), 0)
R_max = max(self.find_maximum_path_sum_recursive(node.right), 0)
# ignore paths with negative sums, since we need to find the maximum sum we should
# ignore any path which has an overall negative sum.
# maximum path sum AT the current node will be equal to the sum from the left subtree +
# the sum from right subtree + val of current node
local_max = L_max + R_max + node.val
# update the global maximum sum
self.global_max = max(self.global_max, local_max)
# maximum sum of any path FROM the current node will be equal to the maximum of
# the sums from left or right subtrees plus the value of the current node
return max(L_max, R_max) + node.val