TAIRREC实施树深度算法

Question

请建议有一种方法可以实现“古典”树深算术的尾部。

import scala.annotation.tailrec

object Tree extends App {

  sealed trait Tree[+A]

  case class Node[A](value: A,
                     left: Option[Tree[A]] = None,
                     right: Option[Tree[A]] = None) extends Tree[A]

  object Node:
    def apply[A](value: A) =
      new Node[A](value = value, left = None, right = None)

    def apply[A](value: A, node: Tree[A]) =
      new Node[A](value = value, left = Some(node), right = None)

    def apply[A](value: A, left: Tree[A], right: Tree[A]) =
      new Node[A](value = value, left = Some(left), right = Some(right))

    def unapply[A](node: Node[A]): (A, Option[Tree[A]], Option[Tree[A]]) =
      (node.value, node.left, node.right)

  def go[A](node: Option[Tree[A]]): Int =
    node match
      case None => 0
      case Some(Node(_, left, right)) => Math.max(go(left), go(right)) + 1

  val tree = Node(value = "root",
    left = Node(value = "a"),
    right = Node(value = "b",
      left = Node(value = "c"),
      right = Node(value = "d")))

  println(go(Some(tree)))

}

我发现一些指示可以使用CPS（持续传递样式）方式 - 但我仍然失败了。

谢谢。

Answer 1

这个问题可能不会有解决方案，这既是尾部递归，高效，并且对所有可能的树都有效（这不是100％真实，这可能是我所能提出的）。让我解释一下我的意思。在尾部递归动作中，返回的表达式必须是计算的值或对函数本身的调用，而返回的表达式/值没有额外的计算，对吗？考虑一下阶乘计算，您要么返回累积值，要么只调用功能本身。现在，在您的情况下，您的树看起来可能是这样的：

        R
      /  \ 
    A     B
   / \   /
  C  D   E
 /
F 

让我们从r开始，两个孩子的节点都可以满足，您要如何计算节点的最大深度？您必须遍历两个子树（A和B）的整个深度，然后返回最大值吗？因此，您在A和B深度的返回值（Math.max）上添加了额外的操作。现在，幸运的是，一种方法可以将表达式转化为尾部递归，但根本不是有效的。

...
// in your else expression where you know that the node is not empty itself
(node.left.isEmpty, node.right.isEmpty) match {
  case (true, true) => currentDepth + 1
  case (true, false) => go(node.right, currentDepth)
  case (false, true) => go(node.left, currentDepth)
  case _ =>
    val leftLDepth = go(node.left, currentDepth)
    val rightDepth = go(node.right, currentDepth)
    // this is were everything gets dirty
    if (leftDepth > rightDepth) {
      go(node.left, currentDepth)
    } else if (rightDepth > leftDepth) {
      go(node.right, currentDepth)
    } else { leftLength }
}

这实际上很糟糕，这是第七天空的时间复杂性。因此，您实际上可以通过尾部递归来完成，但是尾随不适合这种情况。并注意这实际上不是TailRec，它可能被编译器接受为TailRec（也许，不确定！）。因为当您计算孩子的节点深度和比较时，每个计算都使用2个stackframes（每个计算也可以有2个孩子，所以...）。

动态编程似乎更合适。

---

Update

我实际上试图实现该方法，并且编译器不接受，因为对该功能的调用不仅在尾部位置：D