二叉树之蛇形遍历

原题

这是一道关于二叉树遍历的题目：leetcode-103

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

例如 [3,9,20,null,null,15,7]：

则返回：

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

很容易理解：一层层输出，奇数层从左到右，偶数则从右到左。

下面，我们先从如何用 JavaScript 描述和构建二叉树开始着手。

二叉树 —— 二叉链表描述

二叉树最基本的元素是节点，它主要由三部分构成：

值（数据）
左子节点指针（引用）
右子节点指针

构造函数如下：

function BNode (val) {
    this.val = val
    // 下面两个指针默认为 null
    this.left = null
    this.right = null
}

构建二叉树

最简单的是先序构建：

function preorderCreateTree (arr) {
  const d = arr.shift() // 为了更好理解，就采用了 shift
  if (d === null || d === undefined) {
    return null
  }
  // 先构建本节点
  const t = new BNode(d)
  // 构建左子树
  t.left = preorderCreateTree(arr)
  // 构建右子树
  t.right = preorderCreateTree(arr)

  return t
}

这颗二叉树的先序构建序列是 [3,9,null,null,20,15,null,null,7]：

然后这棵树还有一种构建序列是 [3,9,20,null,null,15,7]（上面已经提到），这种构建方法可以理解为：
一层层构建，先左后右。

具体实现为：

function levelCreateTree (arr) {
  let n;
  let i = 0
  let d = arr[i++]
  if (!d) {
    return null
  }
  const rootNode = new BNode(d)
  let queue = [rootNode]
  while (queue.length) {
    // 出队
    n = queue.shift()
    if (!n) continue
    // 先构建左子节点
    d = arr[i++]
    n.left = d ? new BNode(d) : null
    queue.push(n.left)
    // 构建右子节点
    d = arr[i++]
    n.right = d ? new BNode(d) : null
    queue.push(n.right)
  }

  return rootNode
}

现在，我们就能很好地解题测试了~

再回到题目

其实这道题就是二叉树层次遍历的变种，如果回到例子中，那么层次遍历会返回：

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

所以我们只需在层次遍历的基础上对偶数层进行反转即可。

层次遍历的实现代码：

function levelOrder (t) {
  if (!t) return []
  let n
  let queue = [t]
  let res = []
  let curr
  let count
  while (queue.length) {
    // 获取这一层的节点数
    count = queue.length
    curr = []
    while (count--) {
      n = queue.shift()
      curr.push(n.val)
      if (n.left) queue.push(n.left)
      if (n.right) queue.push(n.right)
    }
    // 存储当前层输出
    res.push(curr)
    // 进入下一层……
  }

  return res
}

层次遍历的关键在于我们如何判断一层的结束（末尾）。上面实现的思路是：当前层遍历完毕后，我们就可以通过当前队列的长度去判断下一层的节点数。

那么，蛇形输出就迎刃而解：

function zigzagLevelOrder (t) {
  if (!t) return []
  let n
  let queue = [t]
  let res = []
  let curr
  let count
  while (queue.length) {
    count = queue.length
    curr = []
    while (count--) {
      n = queue.shift()
      curr.push(n.val)
      if (n.left) queue.push(n.left)
      if (n.right) queue.push(n.right)
    }
    // 判断当前层奇偶
    if (!(res.length & 1)) {
      // 奇数层
      res.push(curr)
    } else {
      res.push(curr.reverse()) // 反转
    }
  }

  return res
}

还有我们可以改变实时遍历的策略，这样就不用对数组进行反转，大大减少时间复杂度：

function zigzagLevelOrder (t) {
  if (!t) return []
  let n
  let queue = [t]
  let res = []
  let curr
  let count
  while (queue.length) {
    count = queue.length
    curr = []
    while (count--) {
      n = queue.shift()
      // 判断当前层奇偶
      if (!(res.length & 1)) {
        curr.push(n.val)
      } else {
        // 从数组头部压入
        curr.unshift(n.val)
      }
      if (n.left) queue.push(n.left)
      if (n.right) queue.push(n.right)
    }
    
    res.push(curr)
  }

  return res
}