Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a binary tree root, return the maximum sum of a subtree. A subtree is defined to be some node in root including all of its descendants. A subtree sum is the sum of all the node values in the subtree. A subtree can be null in which case its sum is 0.
Constraints
1 ≤ n ≤ 100,000 where n is the number of nodes in root3 / \ 0 2 / 0
Compute the Maximum Subtree Sum in a Binary Tree with DFS Algorithm
We can use the Recursive DFS (Depth First Search) Algorithm to compute the sum of any given subtree, and then we just need to update the maximum sum that we have seen so far.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maximumSubtreeSum(self, root): ans = -math.inf def dfs(root): nonlocal ans if not root: return 0 x = dfs(root.left) + dfs(root.right) + root.val ans = max(ans, x) return x dfs(root) return max(0, ans) |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maximumSubtreeSum(self, root):
ans = -math.inf
def dfs(root):
nonlocal ans
if not root:
return 0
x = dfs(root.left) + dfs(root.right) + root.val
ans = max(ans, x)
return x
dfs(root)
return max(0, ans) Time complexity is O(N) and the space complexity is O(N) where N is the number of the nodes in the binary tree.
See also: Teaching Kids Programming – BFS Algorithm to Compute the Maximum Depth of the Binary Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Reverse a Graph (Adjacency List)
Next Post: How to Truncate a String in PHP?
