ZigZag Tree Traversa

//Method 1:- Single pass O(n)
/*
Logic:
We will use deque for storing the nodes of tree in level order and we will keep a flag which will alternate it's
value at every level.Once you push the left and right node at back and pop from front.and second time
you push right and left from from and pop from back.
*/

from collections import deque
class Solution:
    def zigZagTraversal(self, root):
        if not root:
            return []
        ans = []
        q = deque()
        q.append(root)
        flag = True
        while q:
            k = len(q)
            for _ in range(k):
                if flag:
                    temp = q.popleft()
                    ans.append(temp.data)
                    if temp.left:
                        q.append(temp.left)
                    if temp.right:
                        q.append(temp.right)
                else:
                    temp = q.pop()
                    ans.append(temp.data)
                    if temp.right:
                        q.appendleft(temp.right)
                    if temp.left:
                        q.appendleft(temp.left)
            flag = not flag
        return ans