Simple python BFS solution

  • 0

    For a tree looks like:

      /    \
    2       3

    We can use BFS to convert it as:

    level 1: 1
    level 2: 2 3
    level 3: 4

    Then the output is the last node on each level (1,3,4).

    Time complexity: O(N) we go through each node exactly once;
    que.popleft() O(1)
    que.append() O(1)

    Space complexity: O(N) we use a 2-D array to store all nodes and use a deque for BFS,

    where N is the size of tree.

      def rightSideView(self, root):
        if not root: return []
        que = collections.deque()
        que.append((root, 0))
        level_tree = []
        while que:
            node, level = que.popleft()
            if len(level_tree) <= level:
                level_tree.append([]) # new level
            if node.left:
                que.append((node.left, level + 1))
            if node.right:
                que.append((node.right, level + 1))
        visible_nodes = []
        for level_nodes in level_tree:
            if level_nodes:
        return visible_nodes

Log in to reply

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