_2265. Count Nodes Equal to Average of Subtree.md

2265. Count Nodes Equal to Average of Subtree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 07, 2024

Last updated : July 09, 2024

---

Related Topics : Tree, Depth-First Search, Binary Tree

Acceptance Rate : 86.38 %

---

Solutions

• m2265 v2 better runtime via static variable.py
• m2265.py
• m2265.js

Python

m2265 v2 better runtime via static variable.py

# 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 averageOfSubtree(self, root: TreeNode) -> int:
        self.counter = 0
        def helper(curr: TreeNode) -> (int, int) : # summ, nodeCount
            if not curr :
                return (0, 0)

            print(curr.val)
            if not curr.left and not curr.right :
                self.counter += 1
                return (curr.val, 1)

            left = helper(curr.left)
            right = helper(curr.right)

            output = (left[0] + right[0] + curr.val, left[1] + right[1] + 1)

            if curr.val == output[0] // output[1] :
                self.counter += 1
            return output
        
        helper(root)
        return self.counter

m2265.py

# 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 averageOfSubtree(self, root: TreeNode) -> int:
        def helper(curr: TreeNode) -> [] : # summ, nodeCount, currSum
            if not curr :
                return [0, 0, 0]
            if not curr.left and not curr.right :
                return [curr.val, 1, 1]

            left = helper(curr.left)
            right = helper(curr.right)

            avg = (left[0] + right[0] + curr.val) // (left[1] + right[1] + 1)
            output = [left[x] + right[x] for x in range(3)]

            if curr.val == avg :
                output[2] += 1

            output[0] += curr.val
            output[1] += 1
            return output

        return helper(root)[2]

JavaScript

m2265.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var averageOfSubtree = function(root) {
    var counter = 0;
    function dfs(curr) {
        if (!curr) {
            return [0, 0];
        }
        let left = dfs(curr.left)
        let right = dfs(curr.right)
        let output = [left[0] + right[0] + curr.val, left[1] + right[1] + 1];

        if (curr.val == Math.floor(output[0] / output[1])) {
            counter++;
        }
        return output;
    }

    dfs(root);
    return counter;
};