Python solution using two stacks


  • 0
    S

    We can print spiral order traversal in O(n) time and O(n) extra space. The idea is to use two stacks. We can use one stack for printing from left to right and other stack for printing from right to left.

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def zigzagLevelOrder(self, root):
            if not root:
                return []
            
            s1 = []
            s2 = []
            res = []
            s1.append(root)
            
            while len(s1) > 0 or len(s2) > 0:
                local = []
                while len(s1) > 0:
                    node = s1.pop()
                    local.append(node.val)
                    if node.left:
                        s2.append(node.left)
                    if node.right:
                        s2.append(node.right)
                
                if len(local) > 0:
                    res.append(local)
                
                local = []
                while len(s2) > 0:
                    node = s2.pop()
                    local.append(node.val)
                    if node.right:
                        s1.append(node.right)
                    if node.left:
                        s1.append(node.left)
                
                if len(local) > 0:
                    res.append(local)
            
            return res
    

Log in to reply
 

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