Python iterative BFS using deque
With even or odd level, change the pop/append direction of the deque accordingly.\n\n```\nfrom collections import deque\nclass Solution:\n    def zigzagLevelOrd
With even or odd level, change the pop/append direction of the deque accordingly.\n\n```\nfrom collections import deque\nclass Solution:\n    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n        if not root:\n            return []\n        \n        dq = deque([root])\n        res = []\n        lvl = 0\n        while dq:\n            size = len(dq)\n            curr = []\n            for i in range(size):\n                if lvl % 2 == 0:\n                    p = dq.popleft()\n                    curr.append(p.val)\n                    if p.left:\n                        dq.append(p.left)\n                    if p.right:\n                        dq.append(p.right)\n                else:\n                    p = dq.pop()\n                    curr.append(p.val)\n                    if p.right:\n                        dq.appendleft(p.right)\n                    if p.left:\n                        dq.appendleft(p.left)\n            res.append(curr)\n            lvl += 1\n        return res\n
[]