103.-binary-tree-zigzag-level-order-traversal.md

103. Binary Tree Zigzag Level Order Traversal

• Medium
• Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Analysis

This is almost the same problem as 102.-binary-tree-level-order-traversal.md. The only difference is that we need to look out for the direction in which the new level is added to the answer. Therefore all we need to do is to add a flag flaging whether we should go in the positive direction or the negative direction.

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        stack=[root]
        if not root:
            return []
        answer=[]
        count=1
        while stack:
            temp=[]
            ans=[]
            for node in stack:
                if node.left:
                    temp.append(node.left)
                if node.right:
                    temp.append(node.right)
                ans.append(node.val)
            stack=temp
            if count==1:
                answer.append(ans)
            else:
                answer.append(reversed(ans))
            count*=-1
        return answer