Python using stack


  • 0

    Here I used total to represent the sum of each level's node values, and count to represent the number of nodes in each level.

    class Solution(object):
        def averageOfLevels(self, root):
            """
            :type root: TreeNode
            :rtype: List[float]
            """
            stack = [(root, 1)] if root else []
            total = collections.defaultdict(int)
            count = collections.defaultdict(int)
            while stack:
                node, level = stack.pop()
                total[level] += node.val
                count[level] += 1
                if node.left:
                    stack.append((node.left, level+1))
                if node.right:
                    stack.append((node.right, level+1))
            return [1.0 * total[level] / count[level] for level in sorted(total.keys())]
    

  • 0

    I don't think defaultdict has a guarantee of being iterated in a certain order, so your last line looks flawed. (Edit: after adding the sorted, it's now ok)


  • 0

    @StefanPochmann
    Not sure about if it guarantee the sorted order either. Thus I made like 10 test cases and all of them shows it has a sorted order. Didn't find anything related after googling 10 minutes... Anyway, let me edit it before I found some evidence. :)


  • 1

    I'm not sure about defaultdict, but for dict the order isn't defined:

    CPython implementation detail: Keys and values are listed in an arbitrary order which is non-random, varies across Python implementations, and depends on the dictionary’s history of insertions and deletions.
    -- https://docs.python.org/2/library/stdtypes.html#dict.items

    I didn't find something like that for defaultdict in the documentation, but since it's a subclass of dict, it's probably equivalent.

    With int keys in CPython you'll likely get away with it because of how it's implemented, but for example with strings it can fail:

    >>> list({i: i for i in range(10)})
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> list({str(i): i for i in range(10)})
    ['1', '0', '3', '2', '5', '4', '7', '6', '9', '8']
    

    That's Python 2 and Python 3.5 behaves similarly. In Python 3.6 the implementation of dict was changed and now it happens to be the insertion order (at least if you only insert):

    >>> list({str(i): i for i in range(10)})
    ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    >>> list({str(i): i for i in range(10)[::-1]})
    ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']
    

    But it's still an implementation detail.


Log in to reply
 

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