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.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class TreeNode {
6 public int val;
7 public TreeNode left;
8 public TreeNode right;
9 public TreeNode(int x) { val = x; }
10}
11
12public class Solution {
13 private Dictionary<int, int> sumFrequency = new Dictionary<int, int>();
14
15 private int PostOrder(TreeNode node) {
16 if (node == null) return 0;
17 int leftSum = PostOrder(node.left);
18 int rightSum = PostOrder(node.right);
19 int totalSum = node.val + leftSum + rightSum;
20 if (sumFrequency.ContainsKey(totalSum)) {
21 sumFrequency[totalSum]++;
22 } else {
23 sumFrequency[totalSum] = 1;
24 }
25 return totalSum;
26 }
27
28 public int[] FindFrequentTreeSum(TreeNode root) {
29 PostOrder(root);
30 int maxFreq = sumFrequency.Values.Max();
31 return sumFrequency.Where(entry => entry.Value == maxFreq).Select(entry => entry.Key).ToArray();
32 }
33}
34
35public class Program {
36 public static void Main() {
37 TreeNode root = new TreeNode(5) {
38 left = new TreeNode(2),
39 right = new TreeNode(-3)
40 };
41 Solution solution = new Solution();
42 int[] result = solution.FindFrequentTreeSum(root);
43 Console.WriteLine(String.Join(", ", result));
44 }
45}
46The C# solution maintains a Dictionary to store each subtree sum and its frequency. Using a post-order traversal, it computes subtree sums and fills the dictionary. After the traversal, it finds the largest frequency and retrieves all subtree sums with this frequency.
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
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.