Simple python BFS solution


  • 0
    Q

    For a tree looks like:

        1
      /    \
    2       3
      \
       4
    

    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
            level_tree[level].append(node.val)
    
            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:
                visible_nodes.append(level_nodes[-1])
                
        return visible_nodes

Log in to reply
 

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