Python BFS using queues


  • 0
    Y
    class Solution(object):
        def rightSideView(self, root):
            if root == None:
                return []
            res = []
            explored = [root]
            frontier = []
            while (explored):
                length = len(explored)
                for i in xrange(length):
                    node = explored.pop(0)
                    if i == length - 1:
                        res.append(node.val)
                    if node.left != None:
                        frontier.append(node.left)
                    if node.right != None:
                        frontier.append(node.right)
                # swap. frontier becomes empty again
                explored, frontier = frontier, explored
            return res

  • 1
    Z

    Alternatively, you can avoid pop(0) by just using the index like node = explored[i].
    Meanwhile, explored, frontier = frontier, []. This may save some time.


Log in to reply
 

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