Simple Python Explanation


  • 7

    Let's first visit every node in the tree and count it's value. We can traverse the tree with a dfs.
    After we have every value counted, let's look at values with the highest count and return all of them.

    count = collections.Counter()
    
    def dfs(node):
        if node:
            count[node.val] += 1
            dfs(node.left)
            dfs(node.right)
            
    dfs(root)
    max_ct = max(count.itervalues())
    return [k for k, v in count.iteritems() if v == max_ct]
    

    If we are unfamiliar with collections.Counter, we could have also counted the values with a simple dictionary, changing two lines:

    count = {}
    count[node.val] = count.get(node.val, 0) + 1
    

  • 0
    R

    Nice Python solution. I have a more awkward solution / slightly less Pythonic solution that I came up with in 5 mins:

        def findMode(self, root):
            arr = []
            def helper(node):
                if not node:
                    return None
                arr.append(node.val)
                helper(node.left)
                helper(node.right)
            helper(root)
            c = collections.Counter(arr)
            a = list(c.most_common())
            arr[:] = []
            arr.append(a[0][0])
            most = a[0][1]
            for i in xrange(1, len(c)):
                if a[i][1] < most:
                    break
                if a[i][1] == most:
                    arr.append(a[i][0])
            return arr

  • 0
    T

    I copy and paste your code ,but it shows :Line 23: ValueError: max() arg is an empty sequence
    whats happening?


  • 1
    M

    @totalawesomeness he didnt check for empty input. here is the fixed solution

    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        count = collections.Counter()
        
        def dfs(node):
            if node:
                count[node.val] += 1
                dfs(node.left)
                dfs(node.right)
                
        dfs(root)
        max_ct = max(count.itervalues())
        return [k for k, v in count.iteritems() if v == max_ct]

  • 0
    L

    Your code doesn't check for the empty case. Also, is count technically sorting the key,value pairs by values from lowest to highest?
    @awice said in Simple Python Explanation:

    count = collections.Counter()

    def dfs(node):
    if node:
    count[node.val] += 1
    dfs(node.left)
    dfs(node.right)

    dfs(root)
    max_ct = max(count.itervalues())
    return [k for k, v in count.iteritems() if v == max_ct]
    Do


  • 0
    G

    @awice But it is not O(1) space ....


Log in to reply
 

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