Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.
The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).
Example 1:
Input: root = [5,2,-3] Output: [2,-3,4]
Example 2:
Input: root = [5,2,-5] Output: [2]
Constraints:
[1, 104].-105 <= Node.val <= 105This 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.
The solution creates a simple binary tree structure and uses a post-order traversal to visit each node in the tree. Each subtree sum is calculated and stored in a hash map, where keys are the sums and values are their frequencies. We then determine the highest frequency sums and return them.
C++
Java
Python
C#
JavaScript
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.
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.
In this C solution, we use a full DFS to traverse through each node and pre-compute all subtree sums, storing them in a hash table that maintains their frequency. The method allows for an efficient retreival of the most frequent sums post traversal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), visiting every node by DFS.
Space Complexity: O(N), storing sums and frequencies.
| Approach | Complexity |
|---|---|
| Post-order Traversal with Hash Map | Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once. |
| Pre-compute and DFS | Time Complexity: O(N), visiting every node by DFS. |
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 views views
Watch 9 more video solutions →Practice Most Frequent Subtree Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor