LeetCode 508: Most Frequent Subtree Sum
Problem Description
Explanation:
To solve this problem, we will perform a post-order traversal of the binary tree to calculate the subtree sum for each node. We will keep track of the frequency of each subtree sum in a hashmap. Finally, we will find the most frequent subtree sum and return all values with the highest frequency.
Algorithm:
- Perform a post-order traversal of the binary tree.
- For each node, calculate the subtree sum (sum of node value, left subtree sum, and right subtree sum).
- Update the frequency of the subtree sum in a hashmap.
- Find the highest frequency.
- Return all values with the highest frequency.
Time Complexity: O(n) where n is the number of nodes in the tree. Space Complexity: O(n) for the hashmap.
:
Solutions
class Solution {
Map<Integer, Integer> frequencyMap = new HashMap<>();
int maxFrequency = 0;
public int[] findFrequentTreeSum(TreeNode root) {
calculateSubtreeSum(root);
List<Integer> result = new ArrayList<>();
for (int key : frequencyMap.keySet()) {
if (frequencyMap.get(key) == maxFrequency) {
result.add(key);
}
}
return result.stream().mapToInt(i -> i).toArray();
}
private int calculateSubtreeSum(TreeNode node) {
if (node == null) return 0;
int sum = node.val + calculateSubtreeSum(node.left) + calculateSubtreeSum(node.right);
frequencyMap.put(sum, frequencyMap.getOrDefault(sum, 0) + 1);
maxFrequency = Math.max(maxFrequency, frequencyMap.get(sum));
return sum;
}
}Related LeetCode Problems
Loading editor...