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.
1using System.Collections.Generic;
using System.Linq;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private Dictionary<int, int> sumFrequency = new Dictionary<int, int>();
private int DFS(TreeNode node) {
if (node == null) return 0;
int leftSum = DFS(node.left);
int rightSum = DFS(node.right);
int totalSum = node.val + leftSum + rightSum;
if (sumFrequency.ContainsKey(totalSum)) {
sumFrequency[totalSum]++;
} else {
sumFrequency[totalSum] = 1;
}
return totalSum;
}
public int[] FindFrequentTreeSum(TreeNode root) {
DFS(root);
int maxFreq = sumFrequency.Values.Max();
return sumFrequency.Where(entry => entry.Value == maxFreq).Select(entry => entry.Key).ToArray();
}
public static void Main() {
TreeNode root = new TreeNode(5) {
left = new TreeNode(2),
right = new TreeNode(-3)
};
Solution solution = new Solution();
int[] result = solution.FindFrequentTreeSum(root);
Console.WriteLine(String.Join(", ", result));
}
}
By metalliferous DFS, the C# solution computes each subtree's sum fostering a dictionary to assess and compare frequency counts, then building an output of sums matching the maximum frequency for application.