Python iterative solution with deque


  • 0
    S
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        curr_queue = collections.deque([root])
        nxt_queue = collections.deque()
        res = []
        curr_res = collections.deque()
        cnt = 0
        while curr_queue or nxt_queue:
            if curr_queue:
                curr = curr_queue.popleft()
                if cnt == 0:
                    curr_res.append(curr.val)
                else:
                    curr_res.appendleft(curr.val)
                if curr.left:
                    nxt_queue.append(curr.left)
                if curr.right:
                    nxt_queue.append(curr.right)
            else:
                curr_queue = nxt_queue
                nxt_queue = collections.deque()
                res.append(curr_res)
                curr_res = collections.deque()
                cnt ^= 1
        res.append(curr_res)
        return list(map(list, res))

Log in to reply
 

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