以下是我对 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
的情况下以更惯用/更实用的方式实现上述内容。想法?
最佳答案
是的,你可以,通过使用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)
。
请注意,我只是在语法上重构了您的代码,但由于我无法编译您的代码,因此无法验证其正确性。如果它没有按预期工作,请发表评论。
关于algorithm - BST 层序遍历的惯用 Kotlin,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50711002/