Iterative Python solution. One queue one while loop


  • 0
    X
    class Solution:
        # @param root, a tree node
        # @return a list of lists of integers
        def zigzagLevelOrder(self, root):
            if not root:
                return []
            level = 0
            result = []
            vals = [root.val]
            cur = [root]
            while cur != []:
                new = []
                result.append(vals)
                vals = []
                if level % 2 == 0:
                    for i in range(len(cur)-1, -1, -1):
                        node = cur[i]
                        if node.right != None:
                            vals.append(node.right.val)
                            new.append(node.right)
                        if node.left != None:
                            vals.append(node.left.val)
                            new.append(node.left)
                else:
                    for i in range(len(cur)-1, -1, -1):
                        node = cur[i]
                        if node.left != None:
                            vals.append(node.left.val)
                            new.append(node.left)
                        if node.right != None:
                            vals.append(node.right.val)
                            new.append(node.right)
                level += 1
                cur = new
            return result

Log in to reply
 

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