1
下面的代码应该通过遍历从红色黑树的根节点到底部的左节点来计算黑节点。黑节点的数量存储在变量black
:将程序样式方法转换为函数样式
fun isBalanced1(): Boolean {
require(!isEmpty()) { "Cannot check empty tree for balance"}
var x = root
var black = 0
while(x != null) {
if(!isRed(x)) {
black++
}
x = x.left
}
return isBalanced(root, black)
}
风格是程序性和它的作品确定。
现在怎么能改变在一个更实用的风格做同样的事情?
这是我想出了:
fun isBalanced1(): Boolean {
require(!isEmpty()) { "Cannot check empty tree for balance" }
val black =
generateSequence(root) { node -> node.left }
.takeWhile { node -> node != null }
.filter { node -> !isRed(node) }.count()
return isBalanced(root, black)
}
它使用一个序列发生器遍历树而节点不是null
,然后过滤黑色的和计数的所有比赛。
这是转换此树遍历代码的正确方法还是Kotlin中有更好的替代方法?
我在这段代码中看不到任何递归?顺便说一句,我会把'.count()'放在换行符后面 – Bergi
@Bergi:你说的是递归。没有递归调用。我编辑了这个问题并删除了它,因为它很混乱。 –
'takeWhile'不是必需的,因为'generateSequence'在遇到的第一个null时停止。 'filter {} .count()'相当于'count {}' – Ilya