# LeetCode 508. Most Frequent Subtree Sum

Created at 2018-02-27 Updated at 2018-02-27 Category LeetCode Tag 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 32-bit 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.

## Table of Content

Site by GoingMyWay using Hexo & Random

I am a ML and RL research student

Hide