为什么这不能递归地工作？

Question

下面是 Scala 中的一个程序。

def range(low : Int, high : Int) : List[Int] = {
    var result : List[Int] = Nil
    result = rangerec(root, result, low, high)
    result
}

private def rangerec(r : Node, l : List[Int], low : Int, high :Int) : List[Int] = {
      var resultList : List[Int] = List()
      if(r.left != null) {
        rangerec(r.left, resultList, low, high)
      } else if(r.right != null) {
        rangerec(r.right, resultList, low, high)
      } else {
        if(r.key >= low && r.key <= high) {
            resultList = resultList ::: List(r.key)
            resultList
        } 
      }
      resultList
}

我在二叉搜索树中创建了范围方法，实现了中序遍历算法。所以它必须递归地工作，但它不打印任何东西，List()。如何修复我的算法？或编辑我的代码？

Answer 1

我不知道 scala，但您需要使用作为参数传递到递归函数的列表 l 并使用 rangerec 函数的输出。

private def rangerec(r : Node, l : List[Int], low : Int, high :Int) : List[Int] = {
      var resultList : List[Int] = l
      if(r.left != null) {
        resultList = rangerec(r.left, l, low, high)
      } else if(r.right != null) {
        resultList = rangerec(r.right, l, low, high)
      } else {
        if(r.key >= low && r.key <= high) {
            resultList = l ::: List(r.key)
        } 
      }
      resultList
}

Answer 2

在函数外部定义您的 resultList，因为我看到您将结果附加到该变量。顺便说一句，顺序遍历也遵循这个规则。访问左，访问根，最后访问右。然而从代码中（虽然我不懂scala），我可以破译你正在访问左，右，最后是根。

等效的递归按顺序打印 javacode 看起来像这样

 public void printOrdered(Node node){
  if(node.left != null){
   printOrdered(node.left); //VISIT LEFT
  }
  System.out.println(node.data); //VISIT ROOT AND PRINT
  if(node.right!=null){
   printOrdered(node.right); //VISIT RIGHT
  }
 }

所以，scala 可能看起来像这样（语法可能是错误的）

private def rangerec(r : Node) : Void = {
      if(r.left != null) {
        rangerec(r.left)
      } 
      resultList = resultList :: List(r.key)
      if(r.right != null) {
        rangerec(r.right)
      }
}

这里 resultList 是一个 List 类型的变量，应该从外部传递。