leetcode_gym/_problems/binaryTreeZigZag.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Binary Tree Zig Zag	2020-07-22	bfs	https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal	Solved

Problem

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

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]
        

Solution

{% highlight python %}

def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:

if not root: return

q = [root]
ans = []
odd = True

while q:
    
    level_len = len(q)
    level = []
    
    for _ in range(level_len):
    
        curr = q.pop(0)

        if curr:
        
            level.append(curr.val)

            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)
    
    if odd:
        ans.append(level)
    else:
        ans.append(reversed(level))
    odd = not odd

return ans

{% endhighlight %}