时间戳

首页 > 解决方案 > 用于 BST 级别顺序遍历的惯用 Kotlin

algorithm - 用于 BST 级别顺序遍历的惯用 Kotlin

问题描述

以下是我对 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
}

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

标签： algorithmdata-structurestreekotlinbinary-search-tree

解决方案

Yes you can, by using a sequence (say, 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
}

And BTW you may use listOfNotNull or listOf().filterNotNull to replace filter(Objects::nonNull).

Note I've just syntaxically refactored your code but since I cannot compile your code I can't verify the correctness of it. If it's not working as expected please leave a comment.

推荐阅读