• 从上到下打印二叉树
  • 题目描述
  • 解答
• 从上到下按层打印二叉树
  • 题目描述
  • 解答
• 从上到下按 Z 字形打印二叉树
  • 解答

---

从上到下打印二叉树

题目描述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印

例如:

给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回：

[3, 9, 20, 15, 7]

提示：

节点总数 <= 1000

解答

传统的 BFS，利用队列先进先出的结构特点

• 首先根节点进队
• 利用循环，只要队列不为空
  • 队首出队，
  • 将队首的左孩子还有右孩子依次入队
• 直到队列为空

// 节点类型定义
class Node {
  this.val = null
  this.left = this.right = null
}

// 方法实现
function bfs(root) {
  if(root === null) return []
  // 存储结果数组
  let res = []
  // 队列维护节点
  let queue = [root]
  let node
  // 每次循环队头出队
  while(node = queue.shift()) {
    res.push(node.val)
    // 将左子树入队
    if(node.left) queue.push(node.left)
    // 将由子树入队
    if(node.right) queue.push(node.right)
  }
  return res
}

bfs(root)

从上到下按层打印二叉树

题目描述

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:

给定二叉树: [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

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

提示：

节点总数 <= 1000

解答

• 跟前面类似，但不能按照每次只出队一个元素的思路解决
• 将每一层所有节点维护到一个队列里，然后利用 while 循环，一次处理完一层所有节点
• 这一层处理完之后，然后递归处理下一层

function bfs(root) {
  if (root == null) return []
  // 用来存储结果数组
  let res = [[root.val]]
  let _bfs = (queue) => {
    // 用来存储当前层的所有节点
    let subQueue = []
    // 用来存储当前层所有节点的值
    let sub = []
    // 遍历完当前层的所有节点
    while (queue.length) {
      let node = queue.shift()
      if (node.left) {
        subQueue.push(node.left)
        sub.push(node.left.val)
      }
      if (node.right) {
        subQueue.push(node.right)
        sub.push(node.right.val)
      }
    }
    // 当 sub 中有值才追加到结果数组中去
    if (sub.length) res.push(sub)
    // 递归处理下一层的所有节点，注意递归终止条件
    if (subQueue.length) _bfs(subQueue)
  }
  _bfs([root])
  return res
}

bfs(root)

从上到下按 Z 字形打印二叉树

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:

给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

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

提示：

节点总数 <= 1000

解答

• 按照 Z 字形打印，与上个题目的差别在输出顺序上
• 可以利用当前节点所在的层数，来决定当前层的遍历顺序，从而实现 Z 字形遍历
• 假设根节点在第一层，那偶数层就需要从右往左输出值，奇数层需要从左往右输出值
• 可以保持遍历的方向不变，始终从左往右，不过在输出值的时候，偶数层需要从头插入，使用 unshift；奇数层使用 push

function bfs() {
  if (root == null) return []
  let level = 0
  let res = []
  let queue = [root]

  let _bfs = (queue) => {
    if (!queue.length) return
    let subQueue = []
    let subRes = []
    let node
    level++
    while (queue.length) {
      node = queue.shift()
      // 奇数层尾部追加 偶数层头部插入
      level % 2 ? subRes.push(node.val) : subRes.unshift(node.val)
      let left = node.left
      let right = node.right
      if (left) {
        subQueue.push(left)
      }
      if (right) {
        subQueue.push(right)
      }
    }
    subRes.length && res.push(subRes)
    _bfs(subQueue)
  }

  _bfs(queue)
  return res
}