C++, DFS. Time: O(n), Space: O(n).

• ``````class Solution {
public:
vector<int> findMode(TreeNode* root) {
unordered_map<int, int> map;
vector<int> result;
int modeCount = getModeCount(root, map);

for(pair<int,int> p : map) {
if(p.second == modeCount) {
result.push_back(p.first);
}
}

return result;

}

/**
* Traverse the tree using depth first search.
* Return the mode count (i.e. The count of a repeated number that occurs the most.) of the tree.
*/
int getModeCount(TreeNode* root, unordered_map<int, int> &map) {
if(root == NULL)
return 0;

if(map.find(root->val) == map.end()) {
map.insert(pair<int, int>(root->val, 1));
}
else {
map[root->val]++;
}

return max(map[root->val], max(getModeCount(root->left, map), getModeCount(root->right, map)));
}
};
``````

• Golang version:

``````func findMode(root *TreeNode) []int {
mp := make(map[int]int)
result := make([]int, 0)
modeCount := getModeCount(root, mp);

for k, v := range mp {
if v == modeCount {
result = append(result, k)
}
}
return result
}

func getModeCount(root *TreeNode, mp map[int]int) int {
if(root == nil) {
return 0
}
if _, ok := mp[root.Val]; ok {
mp[root.Val]++
} else {
mp[root.Val]=1;
}

return max(mp[root.Val], max(getModeCount(root.Left, mp), getModeCount(root.Right, mp)))
}

func max(a int, b int) int {
if a < b {
return b
} else {
return a
}
}
``````

Javascript version:

``````var findMode = function(root) {
var mp = {}
var result = []
var modeCount = getModeCount(root, mp)

for(var prop in mp) {
if(mp[prop] == modeCount) {
result.push(parseInt(prop))
}
}
return result
};

var getModeCount = function(root, mp) {
if(!root) return 0
if (root.val in mp) {
mp[root.val]++
} else {
mp[root.val] = 1
}

return Math.max(mp[root.val], Math.max(getModeCount(root.left, mp), getModeCount(root.right, mp)));
}
``````

• The second part of the coded can be more concise as

``````    int getModeCount(TreeNode* root, unordered_map<int, int> &map) {
if(root == NULL)
return 0;
map[root->val]++;

return max(map[root->val],max(getModeCount(root->left, map),getModeCount(root->right, map)));
``````

Overall a nice solution!

``}``

• @lancerts

``````    int findModeHelper(TreeNode *root, unordered_map<int,int> &dict) {
if (!root)return 0;
else return max(++dict[root->val], max(findModeHelper(root->left, dict), findModeHelper(root->right, dict)));
}``````

• Hi,
I think one calling of map_find function takes O(n) (in worst case) because key value has no limitation.
And getModeCount is called n-times.
So I guess your code is O(n^2).

• @gurugio
i think the time is like this:
map : map_find : O(lgn) <Red-Black_Tree>
unordered map : map_find : O(1) <Hash-Table>,more precisely,is the time of
hashfunction(map->first)

• @lancerts yes

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.