LeetCode 102. 二叉树的层序遍历 Binary Tree Level Order Traversal （广度优先搜索（BFS））
LeetCode 102. 二叉树的层序遍历 Binary Tree Level Order Traversal （广度优先搜索（BFS））
102. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]- Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its level order traversal as:
[
[3],
[9,20],
[15,7]
]解法
这道题适合用广度优先搜索（BFS），以及 BFS 适用于什么样的场景。
DFS（深度优先搜索）和 BFS（广度优先搜索）就像孪生兄弟，提到一个总是想起另一个。然而在实际使用中，我们用 DFS 的时候远远多于 BFS。那么，是不是 BFS 就没有什么用呢？
如果我们使用 DFS/BFS 只是为了遍历一棵树、一张图上的所有结点的话，那么 DFS 和 BFS 的能力没什么差别，我们当然更倾向于更方便写、空间复杂度更低的 DFS 遍历。不过，某些使用场景是 DFS 做不到的，只能使用 BFS 遍历。这就是我们要介绍的两个场景：「层序遍历」、「最短路径」。
给定一个二叉树，返回其按层序遍历得到的节点值。 层序遍历即逐层地、从左到右访问所有结点。
什么是层序遍历呢？简单来说，层序遍历就是把二叉树分层，然后每一层从左到右遍历：
乍一看来，这个遍历顺序和 BFS 是一样的，我们可以直接用 BFS 得出层序遍历结果。然而，层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。
那么，怎么给 BFS 遍历的结果分层呢？我们首先来观察一下 BFS 遍历的过程中，结点进队列和出队列的过程：
代码
package i.levelOrder
import java.util.*
/**
* @author: Jack
* 2020-05-13 22:04
*
*/
fun main() {
val root = TreeNode(3)
root.left = TreeNode(9)
val right = TreeNode(20)
right.left = TreeNode(15)
right.right = TreeNode(7)
root.right = right
val ans = levelOrder(root)
println(ans)
val ans2 = levelOrderRecursive(root)
println(ans2)
}
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
/**
* Queue Solution
*/
fun levelOrder(root: TreeNode?): List<List<Int>> {
val ans = mutableListOf<List<Int>>()
if (null != root) {
val queue = LinkedList<TreeNode>()
queue.offer(root)
while (queue.isNotEmpty()) {
val levelList = mutableListOf<Int>()
val size = queue.size
// 此处的for循环会把当前 level 层的所有元素poll出来,同时把下一层待遍历的节点放入队列
for (i in 0..size - 1) {
// removes the head (first element) of this list
val node = queue.poll()
levelList.add(node.`val`)
// 把下一层待遍历的节点放入队列尾部 tail (last element) of this list.
node.left?.let { left -> queue.offer(left) }
node.right?.let { right -> queue.offer(right) }
}
// 每层的List值,存放到ans中
ans.add(levelList)
}
}
return ans
}
fun levelOrderRecursive(root: TreeNode?): List<List<Int>> {
val ans = mutableListOf<MutableList<Int>>()
visitLevel(ans, 0, root)
return ans
}
fun visitLevel(ans: MutableList<MutableList<Int>>, level: Int, node: TreeNode?) {
if (null == node) return
// level 从0 (root) 开始,此时 ans.size = 0; 每层的值存在 levelList 中. 这地方的代码非常巧妙.
if (ans.size == level) {
val levelList = mutableListOf<Int>()
ans.add(levelList)
}
// 当前节点值存到 levelList 中
ans[level].add(node.`val`)
val left = node.left
val right = node.right
if (null != left)
visitLevel(ans, level + 1, left)
if (null != right)
visitLevel(ans, level + 1, right)
}
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}参考资料
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。