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#include <iostream>
2#include <unordered_map>
3#include <vector>
4using namespace std;
5
6struct TreeNode {
7 int val;
8 TreeNode *left, *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12class Solution {
13public:
14 unordered_map<int, int> sumFrequency;
15
16 int postOrder(TreeNode* root) {
17 if (!root) return 0;
18 int leftSum = postOrder(root->left);
19 int rightSum = postOrder(root->right);
20 int totalSum = root->val + leftSum + rightSum;
21 sumFrequency[totalSum]++;
22 return totalSum;
23 }
24
25 vector<int> findFrequentTreeSum(TreeNode* root) {
26 postOrder(root);
27 int maxFreq = 0;
28 for (auto &entry : sumFrequency) {
29 if (entry.second > maxFreq) {
30 maxFreq = entry.second;
31 }
32 }
33 vector<int> result;
34 for (auto &entry : sumFrequency) {
35 if (entry.second == maxFreq) {
36 result.push_back(entry.first);
37 }
38 }
39 return result;
40 }
41};
42
43int main() {
44 TreeNode* root = new TreeNode(5);
45 root->left = new TreeNode(2);
46 root->right = new TreeNode(-3);
47 Solution sol;
48 vector<int> result = sol.findFrequentTreeSum(root);
49 for (int val : result) {
50 cout << val << " ";
51 }
52 return 0;
53}
54The C++ solution involves creating an unordered_map (hash map) to store the frequency of each subtree sum. We perform a post-order traversal to compute these sums, and after computing all sums, we find the highest frequency. This frequency is used to collect all subtree sums that are equally frequent for the final 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
Adopting DFS within JavaScript, it facilitates frequent sum calculations via a Map, promptly storing frequencies and subsequently selecting sums that prevail most frequently, sealing the solution with DFS efficacy.