Scala：如何计算二叉树叶子中所有元素的总和？

Question

我正在通过书中的练习来学习 Scala "Scala for the Impatient"。给定以下用 case 类对二叉树建模的方法，一个问题要求 计算叶子 .

中所有元素的总和

sealed abstract class BinaryTree
case class Leaf(value: Int) extends BinaryTree
case class Node(left: BinaryTree, right: BinaryTree) extends BinaryTree

我的解决方案如下，按预期工作。但是，我使用的是 MutableList 并且因为 Scala 支持不变性，所以我想知道 是否有办法使用 List?

def leafSum(tree: BinaryTree): Int = {
  collectLeaves(tree) { MutableList[Int]() }.sum
}

private def collectLeaves(tree: BinaryTree)(leaves: MutableList[Int]): MutableList[Int] = tree match {
  case Node(left, right) =>
      collectLeaves(left)(leaves); collectLeaves(right)(leaves)
  case Leaf(value) => leaves += value
}

Answer 1

使用列表不是一个好主意，因为当您连接两个列表时，您将不得不复制它们的内容，因此每次遇到节点时都需要进行 O(n) 复杂度操作。

如果你真的想用列表来做，你可以这样做：

def leafSum(tree: BinaryTree): Int = {
  collectLeaves(tree).sum
}

private def collectLeaves(tree: BinaryTree): List[Int] = tree match {
  case Node(left, right) => collectLeaves(left) ::: collectLeaves(right)
  case Leaf(value) => List(value)
}

尽管我认为直接计算总和更好，因为您不需要将值存储在叶子中：

def sum(tree: BinaryTree): Int = tree match {
  case Node(left, right) => sum(left) + sum(right)
  case Leaf(value) => value
}

Answer 2

这是一种不使用我认为相当优雅的辅助方法的递归方法。请注意，它不是尾递归的，并且会运行大输入内存不足。

def leafSum(tree: BinaryTree): Int = tree match{
  case leaf:Leaf => leaf.value
  case node:Node => leafSum(node.left) + leafSum(node.right)
}

Scala：如何计算二叉树叶子中所有元素的总和？

Scala: How to compute the sum of all elements in the leaves of a Binary Tree?

binary-tree

scala

sum

immutability

case-class