Python with a queue and a stack


  • 0
    B
    class Solution(object):
        def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        queue = collections.deque()
        stack = []
        rst = []
        layer = 0
        
        if not root:    return []
        stack.append(root)
        
        #in every level, <int>n represent the #childnode in this level;
        #                <list>temp represent the node.val in this level
        #                <int>layer indicate left2right or right2left
        while stack:
            n = len(stack)
            i = 0
            temp = []
            layer += 1
            
            #store the childnode in queue.
            while i < n:
                p = stack.pop()
                temp.append(p.val)
                if layer % 2:
                    if p.left:  queue.appendleft(p.left)
                    if p.right: queue.appendleft(p.right)
                else:
                    if p.right: queue.appendleft(p.right)
                    if p.left:  queue.appendleft(p.left)
                i += 1 
            rst.append(temp)
            
            #when level ends, stack.push(queue.pop())one by one.
            j = 0
            len_queue = len(queue)
            while len(stack) < len_queue:
                stack.append(queue.pop())
                j += 1
                
        return rst

Log in to reply
 

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