Very Simple


  • 0
    A

    Just traverse using BFS and if level is even then store in normal order else store level elements in reversed order

    # 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]]
            """
            # First find out height 
            height = self.height(root)
            result = []
            # Here the approch is BFS 
            # Hence to simulate these conditions we will use simple for loop 
            for i in range(height):
                output = self.printLevelOrder(root,i, [])
                if i % 2 == 0:
                    result.append(output)
                else:
                    result.append(list(reversed(output)))
            return result
        
        # This function basically reaches to the level first then appends result to it 
        def printLevelOrder(self, node, height, result):
            if node == None:
                return 
            # If reached to level add val
            if(height == 0):
                result.append(node.val)
            # Else go left and right with one less level
            # Here what you are doing is that decreasing height by 1 until you get height 0 which is nothing but desired level
            # So lets say we want to reach level 2 then we will pass height as 2 then decrease it till becomes zero and simultanously go deep               into tree at every recursive call
            if height > 0:
                self.printLevelOrder(node.left, height-1, result)
                self.printLevelOrder(node.right, height-1, result)
            return result
        
        # Find out height 
        def height(self, root):
            if root == None:
                return 0
            return 1+ max(self.height(root.left),self.height(root.right))
    

Log in to reply
 

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