子树的最大平均值

Submission

运行时间: 28 ms

内存: 18.7 MB

# 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:
        def dfs(root):
            if not root:
                return (0, 0)
            left = dfs(root.left)
            right = dfs(root.right)
            total = left[0] + right[0] + root.val
            count = left[1] + right[1] + 1
            self.res = max(self.res, total/count)
            return (total, count) # not (count, total)
        self.res = 0
        dfs(root)
        return self.res

Explain

该题解通过深度优先搜索（DFS）遍历整棵树，计算每个子树的节点总和与节点数量。对于每个节点，递归地获得其左右子树的节点总和和节点数量，然后加上当前节点的值计算出以当前节点为根的子树的总和与节点数量。利用这两个值，计算当前子树的平均值，并更新全局最大平均值。这个过程通过一个辅助函数dfs实现，它返回一个元组，包含子树的总值和节点数。全局最大平均值通过一个类变量self.res维护，每次计算完一个子树的平均值后，都检查并更新这个最大值。

时间复杂度: O(n)

空间复杂度: O(h)

# 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:
        def dfs(root):
            if not root:
                return (0, 0) # 当前节点为空，返回总和为0，计数为0
            left = dfs(root.left) # 计算左子树的总和和节点数
            right = dfs(root.right) # 计算右子树的总和和节点数
            total = left[0] + right[0] + root.val # 当前子树的总和
            count = left[1] + right[1] + 1 # 当前子树的节点数
            self.res = max(self.res, total/count) # 更新最大平均值
            return (total, count) # 返回当前子树的总和和节点数
        self.res = 0 # 初始化最大平均值
        dfs(root) # 从根节点开始DFS
        return self.res # 返回最大平均值

Explore

在这个问题中，目标是找到具有最大平均值的子树。平均值是一个表示所有节点值的总体代表性指标。它通过总和除以节点数来计算，能够反映出一个子树所有节点值的平均大小，这是衡量数据集中心趋势的一个直观和有效的方法。使用其他统计指标如中位数或模数虽然也能提供信息，但不如平均值来得直接和明确地反映所有节点值的综合情况。

当递归遇到一个null节点时，返回的元组为(0, 0)是合适的处理方式。这是因为null节点不包含任何值，也不应该对节点数量有任何贡献。因此，这种处理方法不会影响父节点的平均值计算，只有非null的子节点才会对总和和节点数产生贡献。这样确保了父节点的平均值只基于实际存在的子节点计算。

在这个解法中，全局变量self.res用于存储遍历过程中遇到的最大平均值。每次通过dfs函数计算得到一个子树的总和和节点数后，会立即计算该子树的平均值，并与self.res进行比较。如果当前子树的平均值更大，self.res就会被更新。这种方式保证了在递归的每一层中，只要找到更大的平均值，全局最大平均值就会即时更新，确保了结果的正确性和实时性。

这种DFS遍历方式是通用的，它适用于所有类型的二叉树。无论是完全二叉树、平衡二叉树还是非平衡二叉树，算法都是通过递归地访问每个节点，计算其子树的总和和节点数，并更新最大平均值。这种方法不依赖于树的结构特性，因此能够有效地处理各种形态的二叉树。