Python solution with detailed explanation


  • 0
    G

    Solution

    Binary Tree Zigzag Level Order Traversal https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

    Algorithm

    • Use 2 stacks and alternate the order of adding to these stacks.
    class Solution(object):
        def zigzagLevelOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            if root == None:
                return []
            s1_rl, s2_lr = [root], []
            output, rl = [], True
            while s1_rl or s2_lr:
                op = []
                if rl:
                    for _ in range(len(s1_rl)):
                        x = s1_rl.pop()
                        op.append(x.val)
                        if x.left:
                            s2_lr.append(x.left)
                        if x.right:
                            s2_lr.append(x.right)
                else:
                    for _ in range(len(s2_lr)):
                        x = s2_lr.pop()
                        op.append(x.val)
                        if x.right:
                            s1_rl.append(x.right)
                        if x.left:
                            s1_rl.append(x.left)                
                rl = not rl
                output.append(op)
            return output
    

Log in to reply
 

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