社区首页 >专栏 >LeetCode 102. 二叉树的层序遍历 Binary Tree Level Order Traversal （广度优先搜索（BFS））

LeetCode 102. 二叉树的层序遍历 Binary Tree Level Order Traversal （广度优先搜索（BFS））

一个会写诗的程序员

修改于 2023-09-21 10:19:52

56500

代码可运行

文章被收录于专栏：一个会写诗的程序员的博客一个会写诗的程序员的博客

运行总次数：0

代码可运行

102. 二叉树的层序遍历

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

示例：

二叉树：[3,9,20,null,null,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],

return 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
}