###### tags: `LeetCode` `Tree` `Recursion` `Medium` `DFS`
# LeetCode #508 [Most Frequent Subtree Sum](https://leetcode.com/problems/most-frequent-subtree-sum/)
### (Medium)
給你一個二元樹的根結點，請你找出出現次數最多的子樹元素和。一個結點的「子樹元素和」定義為以該結點為根的二元樹上所有結點的元素之和（包括結點本身）。

你需要返回出現次數最多的子樹元素和。如果有多個元素出現的次數相同，返回所有出現次數最多的子樹元素和（不限順序）。

---
使用unordered_map記數, DFS遍歷(需處理每個節點作為根節點的樹和, 以及該節點作為其父節點的左(右)子節點的合, 因此要將節點合放入unordered_map中, 同時回傳節點和)。並且同時記錄次數最多的和的次數(maxCount)。

全部DFS做完之後,　遍歷unordered_map, 將次數符合maxCount的key放入數組中, 最後回傳數組即可。

---

class Solution {
public:
    int maxCount=0;
    unordered_map<int,int> c;
    vector<int> findFrequentTreeSum(TreeNode* root) {
        dfs(root, c);
        vector<int> ans;
        for(auto& s:c){
            if(s.second==maxCount)ans.push_back(s.first);
        }
        return ans;
    }
    
    int dfs(TreeNode* node, unordered_map<int,int>& c){
        if(!node)return 0;
        int sum=node->val+dfs(node->left, c)+dfs(node->right, c);
        maxCount=max(++c[sum], maxCount);
        return sum;
    }
};