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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int AverageOfSubtree(TreeNode root) {
int count = 0;
Stack<(TreeNode, bool)> stack = new Stack<(TreeNode, bool)>();
Dictionary<TreeNode, (int, int)> nodeData = new Dictionary<TreeNode, (int, int)>();
stack.Push((root, false));
while (stack.Count > 0) {
var (node, visited) = stack.Pop();
if (node != null) {
if (visited) {
int leftSum = node.left != null ? nodeData[node.left].Item1 : 0;
int leftCount = node.left != null ? nodeData[node.left].Item2 : 0;
int rightSum = node.right != null ? nodeData[node.right].Item1 : 0;
int rightCount = node.right != null ? nodeData[node.right].Item2 : 0;
int totalSum = leftSum + rightSum + node.val;
int totalCount = leftCount + rightCount + 1;
nodeData[node] = (totalSum, totalCount);
if (node.val == totalSum / totalCount) count++;
} else {
stack.Push((node, true));
stack.Push((node.right, false));
stack.Push((node.left, false));
}
}
}
return count;
}
}The C# solution utilizes an explicit stack to perform a post-order traversal. It uses a dictionary to store the sum and count for each node. The node is processed twice: first to traverse its children and then to calculate its subtree's sum and count.