Iterative solution in Python

  • 0
    # 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):
            :type root: TreeNode
            :rtype: List[List[int]]
            if root == None:    return []
            res, cur_level, direction = [], [root], True
            while cur_level:
                tmp = [x.val for x in cur_level]
                if direction:    res.append(tmp)
                else:   res.append(tmp[::-1])
                direction = not direction
                # prepare next level
                next_level = []
                for x in cur_level:
                    if x.left!=None:    next_level.append(x.left)
                    if x.right!=None:   next_level.append(x.right)
                cur_level = next_level
            return res

Log in to reply

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