5-line fast iterative python solutions (48ms)


  • 0
    C

    Based on my shared solution for Binary Tree Level Order Traversal, either reverse the answer at the end, or add new element at the beginning in each loop. All of these variation should be O(n), where n is the total number of nodes.


    (I) Simply reverse `ans` at the end, **5-line, 48ms**
    def levelOrderBottom(self, root):
        ans, level = [], [root]
        while root and level:
            ans.append([node.val for node in level])            
            level = [kid for n in level for kid in (n.left, n.right) if kid]
        return ans[::-1]        
    

    (II) Add a sublist at the beginning of ans in every level
    (a)
    def levelOrderBottom(self, root):
        ans, level = [], [root]
        while level and level[0]:
            ans= [[node.val for node in level]] + ans         
            level = [kid for n in level for kid in (n.left, n.right) if kid]
        return ans
    

    (b) use `ans[:0]=[[sublist]]`
    def levelOrderBottom(self, root):
        ans, level = [], [root]
        while root and level:
            ans[:0] = [[node.val for node in level]]
            level = [kid for n in level for kid in (n.left, n.right) if kid]
        return ans
    

Log in to reply
 

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