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.
1from collections import defaultdict
2from typing import List
3
4class TreeNode:
5 def __init__(self, val=0, left=None, right=None):
6 self.val = val
7 self.left = left
8 self.right = right
9
10class Solution:
11 def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
12 def postOrder(node):
13 if not node:
14 return 0
15 left_sum = postOrder(node.left)
16 right_sum = postOrder(node.right)
17 total_sum = node.val + left_sum + right_sum
18 sum_frequency[total_sum] += 1
19 return total_sum
20
21 sum_frequency = defaultdict(int)
22 postOrder(root)
23 max_freq = max(sum_frequency.values(), default=0)
24 return [s for s, freq in sum_frequency.items() if freq == max_freq]
25
26# Test case
27root = TreeNode(5, TreeNode(2), TreeNode(-3))
28sol = Solution()
29print(sol.findFrequentTreeSum(root)) # Output: [2, -3, 4]
30This Python solution uses a defaultdict to count the frequency of each subtree sum as they are computed in a post-order tree traversal. After collecting all sums, it finds the maximum frequency and gathers all sums with this frequency for 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.