Last updated on July 18th, 2024 at 10:43 pm
Here, We see Most Frequent Subtree Sum LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Hash Table, Tree
Companies
Amazon
Level of Question
Medium
![Most Frequent Subtree Sum LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Most Frequent Subtree Sum LeetCode Solution
Table of Contents
Problem Statement
Given the root
of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.
The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).
Example 1:
![freq1 tree](https://i0.wp.com/assets.leetcode.com/uploads/2021/04/24/freq1-tree.jpg?w=1400&ssl=1)
Input: root = [5,2,-3]
Output: [2,-3,4]
Example 2:
![freq2 tree](https://i0.wp.com/assets.leetcode.com/uploads/2021/04/24/freq2-tree.jpg?w=1400&ssl=1)
Input: root = [5,2,-5]
Output: [2]
1. Most Frequent Subtree Sum LeetCode Solution C++
class Solution { public: int solve(TreeNode* root,unordered_map<int,int> &mp,int& x){ if(root ==NULL)return 0; int l = solve(root->left,mp,x); int r = solve(root->right,mp,x); x = max(x,++mp[root->val+l+r]); return root->val+l+r; } vector<int> findFrequentTreeSum(TreeNode* root) { int x = -1; unordered_map<int,int> mp; solve(root,mp,x); vector<int> ans; for(auto &i: mp){ if(i.second == x){ ans.push_back(i.first); } } return ans; } };
2. Most Frequent Subtree Sum LeetCode Solution Java
class Solution { Map<Integer,Integer> map = new HashMap(); int mostFreq = 0; public int[] findFrequentTreeSum(TreeNode root) { postorder(root); ArrayList<Integer> temp = new ArrayList(); for(int i : map.keySet()){ if(map.get(i) == mostFreq)temp.add(i); } int []res = new int[temp.size()]; for(int i = 0;i< temp.size();i++){ res[i] = temp.get(i); } return res; } public int postorder(TreeNode root){ if(root == null)return 0; int left = postorder(root.left); int right = postorder(root.right); int sum = left + right + root.val; map.put(sum,map.getOrDefault(sum,0) + 1); mostFreq = Math.max(mostFreq,map.get(sum)); return sum; } }
3. Most Frequent Subtree Sum Solution JavaScript
var findFrequentTreeSum = function(root) { const counts = {}; const max = { val: -Infinity }; dfs(root, counts, max); const sums = []; for (let key in counts) { if (counts[key] === max.val) sums.push(parseInt(key)); } return sums; }; function dfs(root, counts, max) { if (!root) return 0; let sum = root.val + dfs(root.left, counts, max) + dfs(root.right, counts, max); counts[sum] = (counts[sum] || 0) + 1; max.val = Math.max(max.val, counts[sum]); return sum; }
4. Most Frequent Subtree Sum Solution Python
class Solution(object): def findFrequentTreeSum(self, root): freq = Counter() def subtree_sum(node): if not node: return 0 s = node.val + subtree_sum(node.left) + subtree_sum(node.right) freq[s] += 1 return s subtree_sum(root) max_freq = max(freq.values()) return [s for s in freq if freq[s] == max_freq]