BFS python solution, easy to follow


  • 0
    Y

    I use deque to traversal and save the level as key and list of node's value in the level.
    You can also find similar solution in my answer to Binary Tree Level Order Traversal. Just to modify the order of iterator.

    class Solution(object):
        def levelOrderBottom(self, root):
            queue=collections.deque([(root,1)])
            dic=collections.defaultdict(list)
            res=[]
            while queue:
                root,level=queue.popleft()
                if not root:
                    continue
                dic[level].append(root.val)
                if root.left:queue.append((root.left,level+1))
                if root.right:queue.append((root.right,level+1))
            for key in sorted(dic,reverse=True):
                res.append(dic[key])
            return res
    

Log in to reply
 

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