5-6 lines fast python solution (48 ms)


  • 48
    C

    level is a list of the nodes in the current level. Keep appending a list of the values of these nodes to ans and then updating level with all the nodes in the next level (kids) until it reaches an empty level. Python's list comprehension makes it easier to deal with many conditions in a concise manner.


    Solution 1, (6 lines)
    def levelOrder(self, root):
        ans, level = [], [root]
        while root and level:
            ans.append([node.val for node in level])
            LRpair = [(node.left, node.right) for node in level]
            level = [leaf for LR in LRpair for leaf in LR if leaf]
        return ans
    

    Solution 2, (5 lines), same idea but use only one list comprehension in while loop to get the next level
    def levelOrder(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
    

    Solution 3 (10 lines), just an expansion of solution 1&2 for better understanding.
    def levelOrder(self, root):
        if not root:
            return []
        ans, level = [], [root]
        while level:
            ans.append([node.val for node in level])
            temp = []
            for node in level:
                temp.extend([node.left, node.right])
            level = [leaf for leaf in temp if leaf]
        return ans

  • 0
    S

    solution 1 is awesome! how would you combine lines 4 and 5 into one giant list comprehension?


  • 0
    C

    Added it to the post (solution 2). It's pretty straightforward but it would look longer. I changed the variable name to make it less than 80 characters in one line.


  • 0
    J

    Solution 2 is terrific.


  • 0

    The Solution2 promotes the best understanding!


  • 11
    E

    Great solution:

    I expanded it a little more for those who don't know list comprehension (such as myself :))

    def levelOrder(self, root):
        ret = []
        
        level = [root]
        
        while root and level:
            currentNodes = []
            nextLevel = []
            for node in level:
                currentNodes.append(node.val)
                if node.left:
                    nextLevel.append(node.left)
                if node.right:
                    nextLevel.append(node.right)
            ret.append(currentNodes)
            level = nextLevel
            
            
        return ret

  • 0
    D

    thank you for sharing your solution.


  • 1
    A

    An alternative solution using the deque data structure. It is a list like object with O(1) appends and pops from both the left and right sides.

    from collections import deque
    def levelOrder(self, root):
        # traverse in order level, keeping track of (row number, current node)
        queue = deque([(0, root)])
        # keep track of the nodes in each row
        d = {}
    
        while queue:
            row, node = queue.popleft()
            if node:
                d[row] = d.get(row, []) + [node.val]
                queue += (row+1, node.left), (row+1, node.right)
    
        # return a list of lists containing node values in increasing order with respect to the row number
        return [d[row] for row in sorted(d.keys())]

  • 0
    G

    @acmiyaguchi What would be space complexity of this solution?


  • 0
    A

    @gangofmumbai-gmail-com
    We need to store each element of the tree in a hash-table keyed by the row, which requires O(n) space. A breadth first search requires worst case O(2^d) space for the queue where d is the depth of the tree. Since the total number of nodes in the tree will be greater than the nodes in a given level of a tree (n >= 2^d), this solution requires O(n) space for completion.


  • 0
    R

    @acmiyaguchi This is the kind of solution good for vertical order tree traversal.


  • 0
    J
    [kid for n in level for kid in (n.left, n.right) if kid]
    

    Thanks for the explanation! I had a hard time figuring out how to flatten this listcomp.

    I used sum(), but this is cleaner.

    sum([[child in [node.left, node.right] if child] for node in nodes], [])
    

Log in to reply
 

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