Meta VO 面试真题解析：二叉搜索树区间平均值（Return Average of Values in a Range in a Binary Search Tree）

Return the average of the values in a given range in a binary search tree.

Example:

[4,11] => avg(6,10,4,9) => return 7.xx

这道题要求在二叉搜索树中统计某个数值区间内所有节点的平均值。由于 BST 左子树都小于当前节点、右子树都大于当前节点，因此可以用 DFS/ 中序遍历结合区间剪枝：当当前节点值小于下界时，只需要继续搜索右子树；当节点值大于上界时，只需要继续搜索左子树；只有节点值落在区间内时才累加总和并计数。最后用总和除以数量即可得到平均值。图中示例区间为 [4,11]，被统计到的值包括 6、10、4、9，结果为 7.xx。