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

## Link

{% embed url="<https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/>" %}

## Problem

给你二叉树的根节点 `root` ，返回其节点值的 **锯齿形层序遍历** 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

{% code overflow="wrap" %}

```
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
```

{% endcode %}

示例2：

{% code overflow="wrap" %}

```
输入：root = [1]
输出：[[1]]
```

{% endcode %}

示例3:

{% code overflow="wrap" %}

```
输入：root = []
输出：[]
```

{% endcode %}

提示：

* 树中节点数目在范围 `[0, 2000]` 内
* `-100 <= Node.val <= 100`

## Solution

{% tabs %}
{% tab title="Go" %}

```go
func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int(nil)
    }

    reverse := func(a []int) {
        n := len(a)
        for i := 0; i < n>>1; i++ {
            a[i], a[n-i-1] = a[n-i-1], a[i]
        }
    }

    ans := [][]int{}
    q := []*TreeNode{root}
    for i := 0; len(q) > 0; i++ {
        tmp := q 
        q = nil
        nums := []int{}
        for _, node := range tmp {
            nums = append(nums, node.Val)
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }

        if i&1 == 1 {
            reverse(nums)
        }
        ans = append(ans, nums)
    }
    return ans
}
```

{% endtab %}

{% tab title="C++" %}

```cpp
```

{% endtab %}
{% endtabs %}