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.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left, right;
6
7 TreeNode(int x) {
8 val = x;
9 }
10}
11
12class Solution {
13 private Map<Integer, Integer> sumFrequency = new HashMap<>();
14
15 private int postOrder(TreeNode root) {
16 if (root == null) return 0;
17 int leftSum = postOrder(root.left);
18 int rightSum = postOrder(root.right);
19 int totalSum = root.val + leftSum + rightSum;
20 sumFrequency.put(totalSum, sumFrequency.getOrDefault(totalSum, 0) + 1);
21 return totalSum;
22 }
23
24 public int[] findFrequentTreeSum(TreeNode root) {
25 postOrder(root);
26 int maxFreq = Collections.max(sumFrequency.values());
27 List<Integer> result = new ArrayList<>();
28 for (Map.Entry<Integer, Integer> entry : sumFrequency.entrySet()) {
29 if (entry.getValue() == maxFreq) {
30 result.add(entry.getKey());
31 }
32 }
33 return result.stream().mapToInt(i -> i).toArray();
34 }
35
36 public static void main(String[] args) {
37 TreeNode root = new TreeNode(5);
38 root.left = new TreeNode(2);
39 root.right = new TreeNode(-3);
40 Solution sol = new Solution();
41 int[] result = sol.findFrequentTreeSum(root);
42 System.out.println(Arrays.toString(result));
43 }
44}
45The Java solution utilizes a HashMap to track the frequency of each subtree sum as it is computed in the post-order traversal. We iterate over the entries in the map to find the maximum frequency, then gather all sums with that frequency to return as 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#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
unordered_map<int, int> freqMap;
int dfs(TreeNode* node) {
if (!node) return 0;
int leftSum = dfs(node->left);
int rightSum = dfs(node->right);
int sum = node->val + leftSum + rightSum;
freqMap[sum]++;
return sum;
}
public:
vector<int> findFrequentTreeSum(TreeNode* root) {
dfs(root);
vector<int> maxFreqSums;
int maxFreq = 0;
for (const auto& entry : freqMap) {
if (entry.second > maxFreq) {
maxFreq = entry.second;
maxFreqSums = {entry.first};
} else if (entry.second == maxFreq) {
maxFreqSums.push_back(entry.first);
}
}
return maxFreqSums;
}
};
int main() {
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(2);
root->right = new TreeNode(-3);
Solution sol;
vector<int> result = sol.findFrequentTreeSum(root);
for (int val : result) {
cout << val << " ";
}
return 0;
}
The C++ solution employs a recursive DFS and records subtree sums in freqMap with their frequencies. After execution, it identifies the maximum frequency, returning all associated sums using depth-first exploration capabilities.