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


  • 6
    C
    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)));
        }
    };
    

  • 0
    R

    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)));
    }
    

  • 1
    L

    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!

    }

  • 0
    C

    @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)));
        }

  • 0
    G

    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).
    Why is your code O(n)?


  • 0
    C

    @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)


  • 0
    X

    @lancerts yes


Log in to reply
 

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