Scala,列表追加在递归函数中不起作用

Scala, list append don't work inside recursive function

所以我正在研究采用二叉树的算法:

sealed trait BT
case object Empty extends BT
case class Node(val x: Int, val left: BT, val right: BT) extends BT

和 return 二叉树,但在递归 dfs 的帮助下没有重复项来搜索树。

  def removeRecurring_dfs(bt: BT, found: List[Int]): BT = {
    def dfs_helper(tree: BT): BT = {
      tree match
        case Empty => Empty
        case Node(x, _, _) if found.contains(x) => dfs_helper(rR(tree))
        case Node(x, Empty, Empty) =>
          x::found
          tree
        case Node(x, left, Empty) =>
          x::found
          Node(x, dfs_helper(left), Empty)
        case Node(x, Empty, right) =>
          x::found
          Node(x, Empty, dfs_helper(right))
        case Node(x, left, right) =>
          x::found
          Node(x, dfs_helper(left), dfs_helper(right))
    }
    def rR(tree: BT): BT = removeNode(tree, findPath(tree))
    dfs_helper(bt)
  }

列表 'found' 最初是空的。 'removeNode' 和 'findPath' 是帮助我实现目标的函数。经过一些测试,我发现

x::found

line 从不工作,即使触发了该行的情况。通过一些 println 操作,结果证明模式匹配按我的意图工作。

我最近开始玩 scala,我不明白是什么导致了这种行为

正如已经指出的那样,List 是不可变的,因此 x :: found 创建一个新的 List,并在 found 列表前面加上元素 x

新的 List 必须在 saved/sent 某处,否则它会丢失并被垃圾收集。

我不知道你的 findPath()removeNode() 方法应该做什么,所以有点难说,但看起来这就是你想要完成的. (Scala-3 语法)

sealed trait BT
case object Empty extends BT
case class Node(x: Int, left: BT, right: BT) extends BT

def removeRecurring_dfs(bt: BT): BT =
  def dfs_helper(tree:BT, found:Set[Int]): (BT,Set[Int]) = tree match
    case Empty => (Empty, found)
    case Node(x, left, right) =>
      if found(x) then
        dfs_helper(rR(tree), found)
      else
        val (lftNode, moreFound)  = dfs_helper(left, found + x)
        val (rgtNode, totalFound) = dfs_helper(right, moreFound)
        (Node(x, lftNode, rgtNode), totalFound)

  def rR(tree: BT): BT = removeNode(tree, findPath(tree))
  dfs_helper(bt, Set())._1