LeetCode 508. Most Frequent Subtree Sum
Created at 20180227 Updated at 20180227 Category LeetCode
Hi again, happy Chinese New Year, it is a long since that last post. Here is a new LeetCode question on HashTable and Tree, here we go.
Question
Given the root of a tree, you are asked to find the most frequent subtree sum. 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). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.
Examples 1
Input:
5
/ \
2 3
return [2, 3, 4], since all the values happen only once, return all of them in any order.
Examples 2
Input:
5
/ \
2 5
return [2], since 2 happens twice, however 5 only occur once.
Note: You may assume the sum of values in any subtree is in the range of 32bit signed integer.
Solution
You can solve this problem in 3 steps
step 1
For each node,visit the node and nodes of its subtrees and add values of each node including itself and return the sum;
step 2
create a map to store the value sum and its counts.
step 3
return the result.
And there is a better solution using poster order visiting method from down to top. As you can see in the code.
Code

