LeetCode 102. 二叉樹的層序遍歷 Binary Tree Level Order Traversal （廣度優(yōu)先搜索（BFS））

102. 二叉樹的層序遍歷

給你一個二叉樹挥下，請你返回其按層序遍歷得到的節(jié)點(diǎn)值揍魂。（即逐層地，從左到右訪問所有節(jié)點(diǎn)）棚瘟。

示例：

二叉樹：[3,9,20,null,null,15,7],

返回其層次遍歷結(jié)果：

[
[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]
]

解法

這道題適合用廣度優(yōu)先搜索（BFS）现斋，以及 BFS 適用于什么樣的場景。

DFS（深度優(yōu)先搜索）和 BFS（廣度優(yōu)先搜索）就像孿生兄弟偎蘸，提到一個總是想起另一個庄蹋。然而在實際使用中，我們用 DFS 的時候遠(yuǎn)遠(yuǎn)多于 BFS迷雪。那么限书，是不是 BFS 就沒有什么用呢？

如果我們使用 DFS/BFS 只是為了遍歷一棵樹章咧、一張圖上的所有結(jié)點(diǎn)的話倦西，那么 DFS 和 BFS 的能力沒什么差別，我們當(dāng)然更傾向于更方便寫慧邮、空間復(fù)雜度更低的 DFS 遍歷调限。不過舟陆，某些使用場景是 DFS 做不到的误澳，只能使用 BFS 遍歷。這就是我們要介紹的兩個場景：「層序遍歷」秦躯、「最短路徑」忆谓。

給定一個二叉樹，返回其按層序遍歷得到的節(jié)點(diǎn)值踱承。層序遍歷即逐層地倡缠、從左到右訪問所有結(jié)點(diǎn)。

什么是層序遍歷呢茎活？簡單來說昙沦，層序遍歷就是把二叉樹分層，然后每一層從左到右遍歷：

乍一看來载荔，這個遍歷順序和 BFS 是一樣的盾饮，我們可以直接用 BFS 得出層序遍歷結(jié)果。然而懒熙，層序遍歷要求的輸入結(jié)果和 BFS 是不同的丘损。層序遍歷要求我們區(qū)分每一層，也就是返回一個二維數(shù)組工扎。而 BFS 的遍歷結(jié)果是一個一維數(shù)組徘钥，無法區(qū)分每一層。

那么肢娘，怎么給 BFS 遍歷的結(jié)果分層呢呈础？我們首先來觀察一下 BFS 遍歷的過程中舆驶，結(jié)點(diǎn)進(jìn)隊列和出隊列的過程：

代碼

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循環(huán)會把當(dāng)前 level 層的所有元素poll出來,同時把下一層待遍歷的節(jié)點(diǎn)放入隊列
            for (i in 0..size - 1) {
                // removes the head (first element) of this list
                val node = queue.poll()
                levelList.add(node.`val`)

                // 把下一層待遍歷的節(jié)點(diǎn)放入隊列尾部 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)
    }

    // 當(dāng)前節(jié)點(diǎn)值存到 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)猪落，非商業(yè)轉(zhuǎn)載請注明出處贞远。

Kotlin開發(fā)者社區(qū)

專注分享 Java、 Kotlin笨忌、Spring/Spring Boot蓝仲、MySQL、redis官疲、neo4j袱结、NoSQL、Android途凫、JavaScript垢夹、React、Node维费、函數(shù)式編程果元、編程思想、"高可用犀盟，高性能而晒，高實時"大型分布式系統(tǒng)架構(gòu)設(shè)計主題。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者