Medium

Count Nodes Equal to Average of Subtree

LAB

The tree is encoded as a level-order array where -1 means null. Return how many non-null nodes equal the integer average of their subtree.

EXAMPLES

Example 1

Input
{
  "values": [
    4,
    8,
    5,
    0,
    1,
    -1,
    6
  ]
}

Output
5

FUNCTION SHAPE

values: intArray→int

SOLUTION NOTE

This is the source's fundamental subtree pattern: return multiple values, here (sum, count), from each postorder call instead of traversing the same subtree repeatedly.

Reveal reference solution +

pythonREFERENCE

def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
    res = 0

    def subtree_info(node):
        if not node:
            return 0, 0
        nonlocal res
        left_sum, left_count = subtree_info(node.left)
        right_sum, right_count = subtree_info(node.right)
        total = node.val + left_sum + right_sum
        count = 1 + left_count + right_count
        if total // count == node.val:
            res += 1
        return total, count

    subtree_info(root)
    return res

TimeO(n)

SpaceO(h)

Open on LeetCode ↗