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.
1
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.
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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MAX_TREE_SIZE 10000
6#define HASH_SIZE 20000
7
8typedef struct TreeNode {
9 int val;
10 struct TreeNode *left, *right;
11} TreeNode;
12
13typedef struct ListNode {
14 int sum;
15 int count;
16 struct ListNode *next;
17} ListNode;
18
19ListNode* hashTable[HASH_SIZE];
20
21int hash(int key) {
22 return abs(key) % HASH_SIZE;
23}
24
25void insertHash(int sum) {
26 int index = hash(sum);
27 ListNode *node = hashTable[index];
28 while (node != NULL) {
29 if (node->sum == sum) {
30 node->count++;
31 return;
32 }
33 node = node->next;
34 }
35 node = (ListNode*)malloc(sizeof(ListNode));
36 node->sum = sum;
37 node->count = 1;
38 node->next = hashTable[index];
39 hashTable[index] = node;
40}
41
42int dfs(TreeNode *root) {
43 if (!root) return 0;
44 int left_sum = dfs(root->left);
45 int right_sum = dfs(root->right);
46 int sum = root->val + left_sum + right_sum;
47 insertHash(sum);
48 return sum;
49}
50
51int* findFrequentTreeSum(TreeNode* root, int* returnSize) {
52 dfs(root);
53 int maxCount = 0;
54 int result[MAX_TREE_SIZE];
55 int idx = 0;
56 for (int i = 0; i < HASH_SIZE; i++) {
57 ListNode *node = hashTable[i];
58 while (node) {
59 if (node->count > maxCount) {
60 maxCount = node->count;
61 idx = 0;
62 result[idx++] = node->sum;
63 } else if (node->count == maxCount) {
64 result[idx++] = node->sum;
65 }
66 node = node->next;
67 }
68 }
69 int *output = (int*)malloc(idx * sizeof(int));
70 memcpy(output, result, idx * sizeof(int));
71 *returnSize = idx;
72 return output;
73}
74
75int main() {
76 TreeNode root = {5, NULL, NULL};
77 TreeNode left = {2, NULL, NULL};
78 TreeNode right = {-3, NULL, NULL};
79 root.left = &left;
80 root.right = &right;
81 int returnSize;
82 int *result = findFrequentTreeSum(&root, &returnSize);
83 for (int i = 0; i < returnSize; i++) {
84 printf("%d ", result[i]);
85 }
86 free(result);
87 return 0;
88}
89In 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.