Meta BST所有节点平均值：空树与精确算术

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 题目目标是全树节点值均值，含根与内部节点；BST排序性质不是必要条件。空树均值无定义，返回None。
• 示例返回(total,count)精确分数的分子分母，调用者按需求用Fraction或浮点转换；不提前逐节点除法。

解题路线

1. 显式DFS每遇节点加val/count，同时push左右孩子。每节点访问一次，结束后total/count。
2. BST可以有重复值，每个节点分别计数；不把值放set。若面试期望double输出，最后转换并说明大整数与精度。
3. 若高频查询动态BST，可每节点维护subtreeSum与subtreeCount，在插入/删除/旋转时同步更新，均值查询O(1)读取根聚合，但每写要维护不变量。

手动走一遍

根5、左1、右9，其右下有9，total24/count4，均值6。仅叶1和9的均值5不符合“所有节点”。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def all_node_average(root):
    """Visit EVERY node, not only leaves; returns exact numerator/denominator pair."""
    if root is None:return None
    total=count=0;stack=[root]
    while stack:
        node=stack.pop();total+=node.val;count+=1
        if node.left is not None:stack.append(node.left)
        if node.right is not None:stack.append(node.right)
    return total,count

复杂度

O(n)时间，显式DFS栈O(h)一般上界O(n)；结果仅常数状态。

易错点与追问

容易失分的边界

• 空树直接除0应显式处理。
• 按层平均后再平均会给每层相同权重，不等于所有节点等权。

继续深挖

• 多个子树平均汇总应使用sum和count加权，不能平均它们的均值。
• 若需滑窗更新或删除节点，缓存计数应随结构变更更新，旧count会污染所有均值。