binary_tree_maximum_path_sum
1from typing import Optional 2from utils import TreeNode 3from math import inf 4 5 6# @leet start 7class Solution: 8 def maxPathSum(self, root: Optional[TreeNode]) -> float: 9 """ 10 This problem asks for the maximum path through a tree's summed up 11 node values. 12 13 For every node, its maximum path is its current value + either its 14 left or right subtree. 15 16 If the left or right subtree have negative values, we would like to 17 drop that value, so we can set it to 0 if the path is negative. 18 19 As we traverse the tree, we want to set the current max path to 20 every node's left + right + current value. 21 This is because paths can go from the left subtree to the node 22 to the right subtree. 23 24 At the end we return the value that corresponds to the max path. 25 """ 26 max_path = -inf 27 28 def traverse(node): 29 nonlocal max_path 30 31 if not node: 32 return 0 33 34 left = max(traverse(node.left), 0) 35 right = max(traverse(node.right), 0) 36 37 max_path = max(max_path, left + right + node.val) 38 39 return max(left + node.val, right + node.val) 40 41 traverse(root) 42 return max_path 43 44 45# @leet end 46 47 48def test(): 49 assert 2 + 2 == 4
class
Solution:
8class Solution: 9 def maxPathSum(self, root: Optional[TreeNode]) -> float: 10 """ 11 This problem asks for the maximum path through a tree's summed up 12 node values. 13 14 For every node, its maximum path is its current value + either its 15 left or right subtree. 16 17 If the left or right subtree have negative values, we would like to 18 drop that value, so we can set it to 0 if the path is negative. 19 20 As we traverse the tree, we want to set the current max path to 21 every node's left + right + current value. 22 This is because paths can go from the left subtree to the node 23 to the right subtree. 24 25 At the end we return the value that corresponds to the max path. 26 """ 27 max_path = -inf 28 29 def traverse(node): 30 nonlocal max_path 31 32 if not node: 33 return 0 34 35 left = max(traverse(node.left), 0) 36 right = max(traverse(node.right), 0) 37 38 max_path = max(max_path, left + right + node.val) 39 40 return max(left + node.val, right + node.val) 41 42 traverse(root) 43 return max_path
9 def maxPathSum(self, root: Optional[TreeNode]) -> float: 10 """ 11 This problem asks for the maximum path through a tree's summed up 12 node values. 13 14 For every node, its maximum path is its current value + either its 15 left or right subtree. 16 17 If the left or right subtree have negative values, we would like to 18 drop that value, so we can set it to 0 if the path is negative. 19 20 As we traverse the tree, we want to set the current max path to 21 every node's left + right + current value. 22 This is because paths can go from the left subtree to the node 23 to the right subtree. 24 25 At the end we return the value that corresponds to the max path. 26 """ 27 max_path = -inf 28 29 def traverse(node): 30 nonlocal max_path 31 32 if not node: 33 return 0 34 35 left = max(traverse(node.left), 0) 36 right = max(traverse(node.right), 0) 37 38 max_path = max(max_path, left + right + node.val) 39 40 return max(left + node.val, right + node.val) 41 42 traverse(root) 43 return max_path
This problem asks for the maximum path through a tree's summed up node values.
For every node, its maximum path is its current value + either its left or right subtree.
If the left or right subtree have negative values, we would like to drop that value, so we can set it to 0 if the path is negative.
As we traverse the tree, we want to set the current max path to every node's left + right + current value. This is because paths can go from the left subtree to the node to the right subtree.
At the end we return the value that corresponds to the max path.
def
test():