# 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).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints:
• The number of nodes in the tree is in the range `[0, 2000]`.
• `-100 <= Node.val <= 100`

### 解題

/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
res := make([][]int, 0)
var bfs func(*TreeNode, int)
bfs = func(n *TreeNode, level int) {
if n == nil { return }
if len(res) == level {
res = append(res, []int{})
}
res[level] = append(res[level], n.Val)
bfs(n.Left, level + 1)
bfs(n.Right, level + 1)
}
bfs(root, 0)
for i:=1; i<len(res); i+=2 {
res[i] = ReverseSlice(res[i])
}
return res
}
func ReverseSlice(s []int) []int {
var r []int
for i := len(s) - 1; i >= 0; i-- {
r = append(r, s[i])
}
return r
}

/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
res := make([][]int, 0)
if root == nil { return res }
stack1 := make([]*TreeNode, 0)
stack2 := make([]*TreeNode, 0)
stack1 = append(stack1, root)
isEven := true
for len(stack1) > 0 || len(stack2) > 0 {
temp:=[]int{}
if isEven {
for len(stack1) != 0 {
node :=stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
temp = append(temp, node.Val)
if node.Left != nil {
stack2 = append(stack2, node.Left)
}
if node.Right != nil {
stack2 = append(stack2, node.Right)
}
}
} else {
for len(stack2) != 0 {
node :=stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
temp = append(temp, node.Val)
if node.Right != nil {
stack1 = append(stack1, node.Right)
}
if node.Left != nil {
stack1 = append(stack1, node.Left)
}
}
}
isEven = !isEven
if len(temp) > 0 {
res = append(res, temp)
}
}
return res
}