给你一棵二叉树的根节点
root
,找出这棵树的 每一棵 子树的 平均值 中的 最大 值。
子树是树中的任意节点和它的所有后代构成的集合。
树的平均值是树中节点值的总和除以节点数。
示例:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIn5GcuEzXlxGctFGel9FOwMTMvwlMx8CX3AzLclTMwIzLcNHZh9GbwV3LcRWYvxGc11yYs1ib1lXasF2Lc12bj5ibj1SZk92Y0VWZs5yc0V2czF2Lc9CX6MHc0RHaiojIsJye.png)
输入:[5,6,1]
输出:6.00000
解释:
以 value = 5 的节点作为子树的根节点,得到的平均值为 (5 + 6 + 1) / 3 = 4。
以 value = 6 的节点作为子树的根节点,得到的平均值为 6 / 1 = 6。
以 value = 1 的节点作为子树的根节点,得到的平均值为 1 / 1 = 1。
所以答案取最大值 6。
提示:
- 树中的节点数介于
到1
之间。5000
- 每个节点的值介于 到
之间。100000
- 如果结果与标准答案的误差不超过
,那么该结果将被视为正确答案。10^-5
思路:
树的问题上递归,
中序遍历找到当前子树的所有节点的值,以及当前字数所有节点的个数,
因而可以计算出当前子树的平均值,
然后把刚刚算出来的平均值跟左右子树的结果对比一下,返回最大值即可。
class Solution(object):
def maximumAverageSubtree(self, root):
"""
:type root: TreeNode
:rtype: float
"""
if not root:
return 0
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
Inorder = inorder(root)
return max(1.0 * sum(Inorder) / len(Inorder), self.maximumAverageSubtree(root.left), self.maximumAverageSubtree(root.right))