检查二叉树在 Scala 中是否平衡

Question

我在Scala中使用案例类和特征定义了一个二叉树结构。我是这样做的：

sealed trait Tree[+T]
case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A]
case class Leaf[A](v: A) extends Tree[A]
case object Empty extends Tree[Nothing]

如果给定一个 Tree 实例，我想检查该实例是否平衡，其中平衡的定义是右侧元素的数量等于左侧元素的数量。

我尝试了以下方法(使用累加器模式)来获得我想要的东西：

sealed trait Tree[+T]
case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A]
case class Leaf[A](v: A) extends Tree[A]
case object Empty extends Tree[Nothing]
def isBalanced[A](tree: Tree[A]) = {
def inner(tree: Tree[A], acc: (Int, Int)): Boolean = tree match {
case n: Node[A] => inner(n.l, (acc._1 + 1, acc._2)) && inner(n.r, (acc._1, acc._2 + 1))
case l: Leaf[A] => inner(tree, acc)
case Empty      => acc._1 == acc._2 
}
inner(tree, (0, 0)) 
}
val node: Node[Int] = Node(1, Node(2, Leaf(3), Leaf(4)), Node(5, Leaf(6), Leaf(7)))
isBalanced[Int](node)

这进入了一个无限循环，我很确定我的逻辑犯了一些愚蠢的错误。我对自己犯错的地方并不自信。

Answer 1

你的错误在case Leaf：它应该调用inner(Empty, acc)。你拥有它的方式，它只是不断调用自己 - 因此无限循环。

这将修复无限循环，但实现仍然是错误的：基本上，你不断下降左分支，递增左acc，直到你到达叶子。然后你比较左边和右边(仍然是零)，然后返回。此实现将始终返回 false，除了树，它只是一个叶节点。

此外，您对平衡树的定义是错误的。 例如，像这样：

A
/ 
B   E
/   / 
C   F  G
/
D

符合定义(左右有三个元素)，但不是真正平衡的。
另一方面，像这样：

A
/ 
B  

与定义不符，但实际上是平衡的。

平衡树的正确定义是一，其中左右子树都是平衡的，它们的高度最多相差一个。

考虑到这一点，我们可以编写一个正确的实现，如下所示(如果它是平衡的，则返回树的高度，否则返回 -1)：

def balanced(root: Tree[_]): Int = root match {
case Empty => 0
case Leaf(_) => 1
case Node(_, left, right) => 
val l = balanced(left)
val r = balanced(right)
if (l < 0 || r < 0 || abs(l - r) > 1) -1 else (l max r) + 1
}