Leetcode Problem 2265. Count Nodes Equal to Average of Subtree

2265. Count Nodes Equal to Average of Subtree

Leetcode Solutions

Depth First Search (DFS) for Subtree Averages

  1. Define a recursive function postOrder that takes a node root and returns a pair of integers: the sum of all nodes and the count of nodes in the subtree rooted at root.
  2. If root is NULL, return (0, 0).
  3. Recursively call postOrder for root.left and root.right, storing the results in left and right respectively.
  4. Calculate nodeSum as the sum of root.val, left sum, and right sum.
  5. Calculate nodeCount as 1 (for the current node) plus the count from left and right.
  6. Compute the average by dividing nodeSum by nodeCount and rounding down.
  7. If the average equals root.val, increment the counter count.
  8. Return the pair (nodeSum, nodeCount).
  9. After the postOrder traversal, return the value of count.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...