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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    // 层序遍历改下
    if root == nil {
        return nil
    }

    queue := []*TreeNode{root}
    res := [][]int{}
    flag := 0
    for len(queue)>0 {
        sz := len(queue)
        list := make([]int, 0, sz)
        for i:=0; i<sz; i++ {
            node := queue[0]
            queue = queue[1:]
            list = append(list, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        if flag%2 == 1 {
            for i:=0; i<len(list)/2; i++ {
                list[i], list[len(list)-i-1] = list[len(list)-i-1], list[i] 
            }
        }
        flag++
        res = append(res, list)
    }
    return res
}