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 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def averageOfSubtree(self, root: TreeNode) -> int:
9 def dfs(node):
10 if not node:
11 return (0, 0)
12 left_sum, left_count = dfs(node.left)
13 right_sum, right_count = dfs(node.right)
14 total_sum = left_sum + right_sum + node.val
15 total_count = left_count + right_count + 1
16 if node.val == total_sum // total_count:
17 self.count += 1
18 return total_sum, total_count
19 self.count = 0
20 dfs(root)
21 return self.countThis Python solution defines a recursive DFS function `dfs` that traverses the tree in a post-order manner. For each node, it computes the sum and count of the subtree rooted at that node. If the node value equals the average (sum // count) of its subtree, the counter `self.count` is incremented.
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.