Teaching Kids Programming: Videos on Data Structures and Algorithms
Given the root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10-5 of the actual answer will be accepted. A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.
Example 1:
Input: root = [5,6,1]
Output: 6.00000Explanation:
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.Example 2:
Input: root = [0,null,1]
Output: 1.00000Constraints:
The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 10^5Hints:
Can you find the sum of values and the number of nodes for every sub-tree ?
Can you find the sum of values and the number of nodes for a sub-tree given the sum of values and the number of nodes of it’s left and right sub-trees ?
Use depth first search to recursively find the solution for the children of a node then use their solutions to compute the current node’s solution.
Recursive Depth First Search Algorithm to Compute the Max Average of a Binary SubTree
Based on the Recursive Function to compute the sum of a binary tree, we can let it also return the number of the nodes. We can use a tuple (immutable list) or list to store both sum and number of nodes. Then we can compute the average and store the maxmimum value of it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | # 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 maximumAverageSubtree(self, root: Optional[TreeNode]) -> float: ans = 0 def dfs(root): if not root: return (0, 0) nonlocal ans left, cnt1 = dfs(root.left) right, cnt2 = dfs(root.right) c = cnt1 + cnt2 + 1 s = left + right + root.val ans = max(ans, s / c) return (s, c) dfs(root) return ans |
# 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 maximumAverageSubtree(self, root: Optional[TreeNode]) -> float: ans = 0 def dfs(root): if not root: return (0, 0) nonlocal ans left, cnt1 = dfs(root.left) right, cnt2 = dfs(root.right) c = cnt1 + cnt2 + 1 s = left + right + root.val ans = max(ans, s / c) return (s, c) dfs(root) return ans
The time and space complexity is O(N) where N is the number of the nodes in the given binary tree.
See also: The Maximum Average Subtree of a Binary Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Three Graph Algorithms: Does Every Vertex Have at least One Edge in Graph?
Next Post: The C Function to Print a Char Array (String) in Hexadecimal