algorithm - BST 层序遍历的惯用 Kotlin

Question

以下是我对 BST 的 Level Order Traversal 的实现:

fun levelOrder(): Iterable<Pair<Key, Int>> {
    class InternalNode(val node: Node<Key>, val level: Int)

    val yetToVisit = emptyQueue<InternalNode>()
    val visited = emptyQueue<Pair<Key, Int>>()

    root?.also { yetToVisit.enqueue(InternalNode(it, 1)) }

    while (!yetToVisit.isEmpty) {
        do {
            val node = yetToVisit.dequeue().also { visited.enqueue(it.node.key to it.level) }
            listOf(node.node.left, node.node.right)
                    .filter(Objects::nonNull)
                    .map { InternalNode(it!!, node.level + 1) }
                    .forEach(yetToVisit::enqueue)
        } while (!yetToVisit.isEmpty && yetToVisit.peek().level == node.level)
    }

    return visited
}

我想知道是否可以在不使用 while 和 do-while 的情况下以更惯用/更实用的方式实现上述内容。想法？

Answer 1

是的，你可以，通过使用sequence(比如，generateSequence):

fun levelOrder(): Iterable<Pair<Key, Int>> {
    class InternalNode(val node: Node<Key>, val level: Int)

    val yetToVisit = emptyQueue<InternalNode>()
    val visited = emptyQueue<Pair<Key, Int>>()
    fun peek() = yetToVisit.dequeue()
            .also { visited.enqueue(it.node.key to it.level) }

    root?.also { yetToVisit.enqueue(InternalNode(it, 1)) }
    if (yetToVisit.isEmpty) return visited
    generateSequence(peek()) { node ->
        if (!yetToVisit.isEmpty && yetToVisit.peek().level == node.level) peek()
        else null
    }.forEach { node ->
        listOfNotNull(node.node.left, node.node.right)
                .map { InternalNode(it, node.level + 1) }
                .forEach(yetToVisit::enqueue)
    }

    return visited
}

顺便说一句，您可以使用 listOfNotNull 或 listOf().filterNotNull 来替换 filter(Objects::nonNull)。

请注意，我只是在语法上重构了您的代码，但由于我无法编译您的代码，因此无法验证其正确性。如果它没有按预期工作，请发表评论。