Python iterative solution (linear time, and linear space) with dummies explanation


  • 1
    # linear time, and linear space complexity
    def levelOrder(self, root):
        level_order_traversal = []
        queue = [(root,0)]
        for node,level in queue:
            if node:
                if level >= len(level_order_traversal):
                    level_order_traversal.append([])
                level_order_traversal[level].append(node.val)
                queue.append((node.left,level+1))
                queue.append((node.right,level+1))
        return level_order_traversal
    

    Explanation: Essentially use a queue because we want to move down the tree levels in a FIFO way so we can also insert into the results array in the correct order.


Log in to reply
 

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