Skip to main content

2-24 102.二叉树的层序遍历

Date：2022-02-27 17:45:52

题目：102. 二叉树的层序遍历​

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

示例​

示例1：

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

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

分析​

层序遍历采用BFS（Breadth-first search）进行，算法为维护队列算法，具体参考.https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/

题解​

function levelOrder(root: TreeNode | null) {
  if (root == null) return []

  const queue: (TreeNode | null)[] = []
  const res: number[][] = []

  queue.unshift(root)

  while (queue.length > 0) {
    const len = queue.length

    const layer: number[] = []
    for (let i = 0; i < len; ++i) {
      const el = queue.pop()
      layer.push(el.val)

      if (el.left != null) {
        queue.unshift(el.left)
      }
      if (el.right != null) {
        queue.unshift(el.right)
      }
    }

    res.push(layer)
  }

  return res
}

扩展问题1：DFS和BFS的区别？​

Deep-first Search and Breadth-first search

详见 [1]

[1] BFS 的使用场景总结：层序遍历、最短路径问题.https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/

[2] LeetCode 例题精讲 | 12 岛屿问题：网格结构中的 DFS.https://mp.weixin.qq.com/s?__biz=MzA5ODk3ODA4OQ==&mid=2648167208&idx=1&sn=d8118c7c0e0f57ea2bdd8aa4d6ac7ab7&chksm=88aa236ebfddaa78a6183cf6dcf88f82c5ff5efb7f5c55d6844d9104b307862869eb9032bd1f&token=1064083695&lang=zh_CN#rd

扩展问题2：数组转二叉树？​

示例​

输入：root = [3, 9, 20, null, null, 15, 7]
输出：
TreeNode111 {
  left: TreeNode111 { left: null, right: null, val: 9 },
  right: TreeNode111 {
    left: TreeNode111 { left: null, right: null, val: 15 },
    right: TreeNode111 { left: null, right: null, val: 7 },
    val: 20
  },
  val: 3
}

分析​

数组转二叉树有两种情况：

  • 未优化的数组

    [2,null,4,null,null,9,8,null,null,null,null,null,null,4]

  • 优化的数组

    [2,null,4,9,8,null,null,4]

题解​

优化数组的版本

// Optimize array to binary tree
function arr2Tree(arr: (number | null)[]) {
  if (arr[0] == null) return null

  const queue: (TreeNode | null)[] = []
  const root = new TreeNode111(arr[0])

  queue.unshift(root)

  let isLeft = true
  for (let i = 1; i < arr.length; ++i) {
    const peekEl = queue[queue.length - 1]

    if (isLeft) {
      if (arr[i] != null) {
        peekEl.left = new TreeNode111(arr[i])
        queue.unshift(peekEl.left)
      }
      isLeft = false
    } else {
      if (arr[i] != null) {
        peekEl.right = new TreeNode111(arr[i])
        queue.unshift(peekEl.right)
      }

      queue.pop()
      isLeft = true
    }
  }

  return root
}

没有优化数组的版本

function arr2tree2(arr: (number | null)[]) {
  return createTreeNode(arr, 1)
}
function createTreeNode(arr: (number | null)[], index: number): TreeNode111 | null {
  if (arr[index - 1] == null) {
    return null
  }

  if (index > arr.length) {
    return null
  }

  const node = new TreeNode111(arr[index - 1])

  node.left = createTreeNode(arr, 2 * index)
  node.right = createTreeNode(arr, 2 * index + 1)

  return node
}

[1] Java 一维数组转换二叉树.https://leetcode-cn.com/circle/article/htJ97s/