solution.md

# 二叉树的锯齿形层序遍历

<p>给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。</p>

<p>例如：<br />
给定二叉树 <code>[3,9,20,null,null,15,7]</code>,</p>

<pre>
    3
   / \
  9  20
    /  \
   15   7
</pre>

<p>返回锯齿形层序遍历如下：</p>

<pre>
[
  [3],
  [20,9],
  [15,7]
]
</pre>


## template

```python
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        import collections

        if not root:
            return []

        res, q = [], collections.deque()
        flag = False
        q.append(root)

        while q:
            temp = []
            flag = not flag
            for _ in range(len(q)):
                node = q.popleft()

                if flag:
                    temp.append(node.val)

                else:
                    temp.insert(0, node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(temp)

        return res
```

## 答案

```python

```

## 选项

### A

```python

```

### B

```python

```

### C

```python

```