- Maximum Average Subtree
中等
https://leetcode.cn/problems/maximum-average-subtree/
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.00000
Explanation:
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.00000
Constraints:
The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 105
相关企业
- 亚马逊 Amazon|8
相关标签
- Tree
- Depth-First Search
- Binary Tree
隐藏提示1 Can you find the sum of values and the number of nodes for every sub-tree ?
隐藏提示2 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 ?
隐藏提示3 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.
- 从叶子节点往上，返回自己的value，并保存在一个list里面。
- 当前节点average = sum(左子树value list + 右子树value list + 自己value) / len
- 把所有average保存在一个list最后返回max
# 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: TreeNode) -> float:
if not root:
return 0
all_average_values = []
self.dfs(root, all_average_values)
print(all_average_values)
return max(all_average_values)
def dfs(self, currnode, all_average_values):
# Stopping condition: leaf node
if not currnode.left and not currnode.right:
all_average_values.append(currnode.val)
return [currnode.val]
left_children, right_children = [], []
if currnode.left is not None:
left_children.extend(self.dfs(currnode.left, all_average_values))
if currnode.right is not None:
right_children.extend(self.dfs(currnode.right, all_average_values))
all_nodes_values = left_children + right_children + [currnode.val]
average_value = sum(all_nodes_values) / len(all_nodes_values)
all_average_values.append(average_value)
return all_nodes_values给定一棵二叉树，查找最大平均值子树。
步骤如下：
- 对于一个根结点root，递归的遍历左右子树，返回左右子树的权值和与节点数目，从而得到根结点root以及所有子孙节点作为子树的权值sum和与节点数目num。
sum = left_sum + right_sum + root.val
num = left_num + right_num + 1
-
比较该子树的平均值和已知最大平均值子树的平均值。更新最大平均值子树。
-
为了避免出现精度问题和除零问题，我们可以把
sum / num > self.avg的判断移项成乘法：
sum > self.avg * num
假设有n个节点。
- 空间复杂度：每个节点记录一个sum和num，空间复杂度O(n)。
- 时间复杂度：每个节点递归访问一次，时间复杂度为O(n)。
# 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:
# 最大平均值子树的平均值
avg = 0.0
def maximumAverageSubtree(self, root: TreeNode) -> float:
if not root:
return 0
self.dfs(root)
return self.avg
def dfs(self, currnode):
if currnode is None:
return 0, 0
# 分别递归求解左右子树的所有权值之和&子树节点数目
left_sum, left_num = self.dfs(currnode.left)
right_sum, right_num = self.dfs(currnode.right)
curr_sum, curr_num = left_sum + right_sum + currnode.val, left_num + right_num + 1
# 如果最大平均值子树为空，或者当前子树平均值大于原maxAverage，更新maxAverage
if curr_sum > self.avg * curr_num: # avoid division by zero
self.avg = curr_sum * 1.0 / curr_num
return curr_sum, curr_num