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

[buuing]

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

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

    3
   / \
  9  20
    /  \
   15   7

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 广度优先搜索

这道题是典型的层序遍历, 你可以选择使用reverse()翻转, 也可以像我一样通过flag来判断倒序插入索引

const zigzagLevelOrder = root => {
  if (!root) return []
  let queue = [root], res = [], flag = true
  while (queue.length) {
    let len = queue.length, tmp = []
    flag = !flag
    for (let i = 0; i < len; i++) {
      let curr = queue.shift()
      tmp[flag ? len - i - 1 : i] = curr.val
      if (curr.left) queue.push(curr.left)
      if (curr.right) queue.push(curr.right)
    }
    res.push(tmp)
  }
  return res
}