Sponsored
Sponsored
This approach involves using a post-order traversal (left, right, root) to compute the sum and count of nodes for each subtree. At each node, the sum of values and the total count of the subtree nodes are determined. The average is calculated by dividing the sum by the count and compared with the node's value. If they are equal, a counter is incremented.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, which accounts for the recursion stack.
1class TreeNode {
2 constructor(val = 0, left = null, right = null) {
3 this.val = val;
4 this.left = left;
5 this.right = right;
6 }
7}
8
9function averageOfSubtree(root) {
10 let count = 0;
11
12 function dfs(node) {
13 if (!node) return [0, 0];
14 const [leftSum, leftCount] = dfs(node.left);
15 const [rightSum, rightCount] = dfs(node.right);
16 const totalSum = leftSum + rightSum + node.val;
17 const totalCount = leftCount + rightCount + 1;
18 if (node.val === Math.floor(totalSum / totalCount)) {
19 count++;
20 }
21 return [totalSum, totalCount];
22 }
23
24 dfs(root);
25 return count;
26}This JavaScript version maintains a similar structure to the Python solution. It uses a recursive function `dfs` to compute the sum and count of each subtree. The calculated average is compared to the current node's value, incrementing a counter if they match.
This approach involves using an iterative method with an explicit stack to perform a post-order traversal. Similar to the recursive method, it calculates the sum and count of the subtree nodes for each node using an additional data structure to simulate recursion.
Time Complexity: O(n), since each node is processed twice.
Space Complexity: O(n), for the stack and the dictionary storing sums and counts for each node.
1class TreeNode {
2 int val;
3
In this Java implementation, an iterative approach is employed using two stacks. The first stack manages the node traversal, while the second boolean stack keeps track of whether each node has been fully processed. A HashMap serves as a storage for each node's subtree sum and count.