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

题目#

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

例如：给定二叉树 [3,9,20,null,null,15,7],

返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

思路#

层序遍历的变种，维护队列，需要从右到左时 reverse 一下。

代码#

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

    queue := []*TreeNode{}
    queue = append(queue, root)

    // 左到右、右到左
    ltr := true
    for len(queue) > 0 {
        level := []int{}
        l := len(queue)
        for i := 0; i < l; i++ {
            n := queue[0]
            queue = queue[1:]

            level = append(level, n.Val)
            if n.Left != nil {
                queue = append(queue, n.Left)
            }
            if n.Right != nil {
                queue = append(queue, n.Right)
            }
        }
        // 左到右的话直接 append
        // 右到左的话做一个 reverse
        if !ltr {
            // reverse 操作
            for i := 0; i < len(level)/2; i++ {
                level[i], level[len(level)-1-i] = level[len(level)-1-i], level[i]
            }
        }
        result = append(result, level)
        ltr = !ltr
    }

    return result
}