My easy to understand Python 3 solution


  • 0
    C

    The strategy here is to do a level order order traversal of the tree. You keep track of the level you're on and you use a boolean to determine which way to insert values into the list for the respective row

    This solution takes linear time and space

    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return [];
        queue = [root];
        currLevel = 1;
        nextLevel = 0;
        output    = [];
        level     = [];
        addRight  = True;
    
        while len(queue) != 0:
            poppedNode = queue.pop(0);
            currLevel -= 1;
    
            if addRight:
                level.append(poppedNode.val);
            else:
                level.insert(0,poppedNode.val);
    
            if poppedNode.left:
                nextLevel += 1;
                queue.append(poppedNode.left);
    
            if poppedNode.right:
                nextLevel += 1;
                queue.append(poppedNode.right);
    
            if currLevel == 0:
                currLevel = nextLevel;
                nextLevel = 0;
                output.append(level);
                level = [];
                if addRight:
                    addRight = False;
                else:
                    addRight = True;
    
        return output;
    

Log in to reply
 

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