Python Iterative solution based on regular inorder traversal


  • 0
    G
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param {TreeNode} root
        # @return {integer[][]}
        def zigzagLevelOrder(self, root):
            levels, result, leftToRight = [[root]], [], True
    
            while levels:
                curLevel = levels.pop()
                curValues, nextLevel = [], []
                for node in curLevel:
                    if node:
                        curValues.append(node.val)
                        nextLevel += [node.left, node.right]
    
                if not leftToRight:
                    curValues.reverse()
                if curValues:
                    result.append(curValues)
                if nextLevel:
                    levels.append(nextLevel)
                leftToRight = not leftToRight
    
            return result

Log in to reply
 

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