二叉树的层序遍历 medium BFS

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

example1:

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[9,20],[15,7]]

example2:

输入：root = [1]

输出：[[1]]

example3:

输入：root = []

输出：[]

解题思路

首先确定题目是二叉树，而且要求我们要分层收集数据，那么则需要通过广度优先搜索来遍历每一层的数据，并将其收集到同一个数组中，最后输出即可。

1. 可以在递归的时候增加节点 level 信息，然后将相同的 level push 进同一个数组即可。
2. 可以使用队列，每次遍历之前都拿到数组的长度，然后根据长度拿到层级的信息，然后将同一层的节点 push 进同一个数组即可。

解题方法

1. 递归

function levelOrder(root: TreeNode | null): number[][] {
  const res: number[][] = []
  if (!root) {
    return res
  }
  function dfs(node: TreeNode | null, level: number) {
    if (!node) {
      return
    }
    if (!res[level]) {
      res[level] = []
    }
    res[level].push(node.val)
    dfs(node.left, level + 1)
    dfs(node.right, level + 1)
  }
  dfs(root, 0)
  return res
}

2. 队列遍历

将 root 节点 push 到队列中，然后遍历队列中的节点，并且在遍历的时候拿到队列的长度，然后根据长度拿到层级的信息，然后将同一层的节点 push 进同一个数组即可。

function levelOrder(root: TreeNode | null): number[][] {
  const res: number[][] = []
  if (!root) {
    return res
  }
  const nodeArr: TreeNode[] = [root]
  while (nodeArr.length) {
    const len = nodeArr.length
    const temp: number[] = []
    for (let i = 0; i < len; i++) {
      const node = nodeArr.shift()
      temp.push(node.val)
      node.left && nodeArr.push(node.left)
      node.right && nodeArr.push(node.right)
    }
    res.push(temp)
  }
  return res
}