Sponsored
Sponsored
This approach involves using a post-order traversal to calculate the subtree sum for each node. We store each computed sum in a hash map or dictionary which keeps track of how many times each sum appears. After the traversal, we determine the maximum frequency of the sums and return the list of all sums that have this maximum frequency.
Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(N), for storing sums in the hash map.
1from collections import defaultdict
2from typing import List
3
4class TreeNode:
5 def __init__(self, val=0, left=None, right=None):
6 self.val = val
7 self.left = left
8 self.right = right
9
10class Solution:
11 def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
12 def postOrder(node):
13 if not node:
14 return 0
15 left_sum = postOrder(node.left)
16 right_sum = postOrder(node.right)
17 total_sum = node.val + left_sum + right_sum
18 sum_frequency[total_sum] += 1
19 return total_sum
20
21 sum_frequency = defaultdict(int)
22 postOrder(root)
23 max_freq = max(sum_frequency.values(), default=0)
24 return [s for s, freq in sum_frequency.items() if freq == max_freq]
25
26# Test case
27root = TreeNode(5, TreeNode(2), TreeNode(-3))
28sol = Solution()
29print(sol.findFrequentTreeSum(root)) # Output: [2, -3, 4]
30This Python solution uses a defaultdict to count the frequency of each subtree sum as they are computed in a post-order tree traversal. After collecting all sums, it finds the maximum frequency and gathers all sums with this frequency for the result.
This method involves pre-computing the subtree sums using a depth-first search (DFS). A map is used to record the number of occurrences of each sum, similar to the first method but differing in traversal style. Instead of post-order, a conventional DFS approach computes sums as the tree is traversed depth-first.
Time Complexity: O(N), visiting every node by DFS.
Space Complexity: O(N), storing sums and frequencies.
1
Using standard DFS, the Java solution captures subtree sums and their frequencies in a sumFrequency map. Identifying the maximum frequency, it collects sums that satisfied the condition iteratively, accumulating the prominent subtree sums.