1

我有一个命令式程序，它从数组反序列化为二叉树。它是一种 BFS 算法。我想知道如何在 Scala 中使用函数式编程概念来做到这一点。

class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
  val value: Int = _value
  val left: TreeNode = _left
  val right: TreeNode = _right
}
def createTree(list: Array[Int]): TreeNode = ???

作为参考，这是 Javascript 中的命令式版本。该算法在此处描述。https://support.leetcode.com/hc/en-us/articles/360011883654-What-does-1-null-2-3-mean-in-binary-tree-representation-

class TreeNode {
  constructor(val){
    this.val = val;
    this.left = this.right = null;
  }
}

function makeTree(arr){
  let root = new TreeNode(arr[0]);
  let q = [root];

  let index = 1;
  while(q.length){
    let node = q.splice(0,1)[0];
    if(arr[index] != null){
      node.left = new TreeNode(arr[index]);
      q.push(node.left);
    }
    index++;

    if(arr[index] != null){
      node.right = new TreeNode(arr[index]);
      q.push(node.right);
    }
    index++;
  }
  return root;
}
4

4 回答 4

2

首先，您可以使用案例类来简化您的树类，您应该使用Option而不是null：

case class Tree(value: Int, left: Option[Tree], right: Option[Tree])

接下来，这里的主要问题是因为你的树是不可变的，它需要使用深度优先的后序遍历来构建，而你的序列化格式需要广度优先的层序遍历。因此，您首先必须反序列化为一个数据结构，然后才能以深度优先顺序遍历该数据结构。以下使用从（行，列）到节点值的映射：

@scala.annotation.tailrec
private def bfsTraverse(
    serialized: List[Option[Int]],
    queue: Queue[(Int, Int)],
    map: Map[(Int, Int), Int]): Map[(Int, Int), Int] = {
  val ((row, col), queueTail) = queue.dequeue
  if (serialized.isEmpty) {
    map
  } else if (serialized.head.isEmpty) {
    bfsTraverse(serialized.tail, queueTail, map)
  } else {
    val newQueue = queueTail.enqueueAll(List((row + 1, col * 2), (row + 1, col * 2 + 1)))
    val newMap = map + ((row, col) -> serialized.head.get)
    bfsTraverse(serialized.tail, newQueue, newMap)
  }
}

现在您可以使用该函数的输出来构建您的Tree：

private def buildTree(row: Int, col: Int, map: Map[(Int, Int), Int]): Option[Tree] = {
  map.get((row, col)).map{value =>
    Tree(value, buildTree(row + 1, col * 2, map), buildTree(row + 1, col * 2 + 1, map))
  }
}
于 2020-05-31T19:35:10.653 回答
2

这个解决方案有点冗长，但使用了一些功能概念并彻底定义了数据结构。

  • 您提供的算法更适用于可变节点。有可能只有一个可变类有一个更短的解决方案，但是这里有两个版本（一个节点类具有可变的左/右和另一个完全不可变的）。
  • 案例类自动提供许多有用的功能，例如比较和友好的打印输出
  • processValues函数尾部递归执行与makeTree您提供的函数等效的任务。
  • @tailrec注释告诉编译器检查函数是否是尾递归的。
  • match使用and关键字的模式匹配case替换了对空值或不同子类型的检查，并且编译器可以检查非详尽的匹配子句。
  • App trait 允许您轻松地将对象（静态类）制作为入口点以运行一些示例。
import scala.annotation.tailrec

sealed trait TreeNode[T]
sealed trait MutableTreeNode[T]
object MutableTreeNode {
  final case class Empty[T]() extends MutableTreeNode[T]
  case class Branch[T](val value: T) extends MutableTreeNode[T] {
    protected var left: MutableTreeNode[T] = Empty()
    protected var right: MutableTreeNode[T] = Empty()
    def setLeft(newLeft: T): Branch[T] = {
      left = Branch(newLeft)
      left.asInstanceOf[Branch[T]] // shouldn't be necessary but compiler requires it
    }
    def setRight(newRight: T): Branch[T] = {
      right = Branch(newRight)
      right.asInstanceOf[Branch[T]]
    }
    override def toString: String = this.toImmutable().toString

    /* converts given node to immutable version */
    private def toImmutable(node: MutableTreeNode[T]): TreeNode[T] = {
      node match {
        case Empty() => TreeNode.Empty()
        case b@Branch(value) => TreeNode.Branch(value, toImmutable(b.left), toImmutable(b.right))
      }
    }
    def toImmutable():TreeNode[T] = toImmutable(this)
  }

  /**
    * Modifies nodes inside of queue
    */
  @tailrec def processValues[T](values: Seq[Option[T]], queue: Seq[MutableTreeNode.Branch[T]]): Unit = {
    (queue, values) match {
      case (Nil, _) => ()
      case (_, Nil) => ()
      case (qHead :: qTail, Some(vLeft) :: Some(vRight) :: vTail) =>
        processValues(vTail, qTail :+ qHead.setLeft(vLeft) :+ qHead.setRight(vRight))
      case (qHead :: qTail, Some(vLeft) :: None :: vTail) =>
        processValues(vTail, qTail :+ qHead.setLeft(vLeft))
      case (qHead :: qTail, None :: Some(vRight) :: vTail) =>
        processValues(vTail, qTail :+ qHead.setRight(vRight))
      case (qHead :: qTail, None :: None :: vTail) =>
        processValues(vTail, qTail)
    }
  }
}
object TreeNode {
  final case class Empty[T]() extends TreeNode[T]
  final case class Branch[T](value: T, left: TreeNode[T], right: TreeNode[T]) extends TreeNode[T]

  def deserialize[T](values: Seq[Option[T]]): TreeNode[T] = {
    values match {
      case Some(headVal) :: tail =>
        val root: MutableTreeNode.Branch[T] = MutableTreeNode.Branch(headVal)
        MutableTreeNode.processValues(tail, Seq(root))
        root.toImmutable()
      case Nil => Empty()
      case _ => throw new RuntimeException("Invalid argument values")
    }
  }
}

object TreeNodeTest extends App {
  val input = Seq(Some(5), Some(4), Some(7), None, None, Some(2), None)
  val treeNode:TreeNode[Int] = TreeNode.deserialize(input)
  println(treeNode)
}
于 2020-06-01T00:26:19.647 回答
1

如前所述，Scalanull尽可能避免，而是更喜欢Option指示值的缺失。

可变变量也被回避，这使得以深度优先而不是广度优先的方式构建 B 树变得更加容易。

因此，您真正需要的只是一个易于使用的广度优先序列化 --to--> 深度优先序列化转换器。

我分两步完成。

//from Breadth-First-Serialization to full tree representation
def BFS2full[A](bfs:IndexedSeq[Option[A]]) :List[List[Option[A]]] = {
  val bfsLen = bfs.length
  if (bfs.isEmpty) Nil
  else
    List(bfs.head) :: List.unfold((List(bfs.head),1)){case (pr,idx) =>
      Option.when(bfsLen > idx){
        val ns = pr.foldLeft((List.empty[Option[A]],idx)){
          case ((acc,x), None) => (acc ++ List(None,None), x)
          case ((acc,x), _) => (acc ++ List(bfs.lift(x).flatten
                                           ,bfs.lift(x+1).flatten), x+2)
        }
        (ns._1, ns)
      }
    }
}

//from full tree representation to Depth-First-Serialization
def toDFS[A](lloa :List[List[Option[A]]]
            ,lvl :Int = 0) :List[Option[A]] = lloa match {
  case Nil => List(None, None)
  case List(None) :: Nil => List(None)
  case List( oa ) :: tl  => oa :: toDFS(tl, lvl)
  case row :: tl => row.drop(lvl*2) match {
    case List(None,None,_*) => List(None, None)
    case List(None, ob ,_*) => None :: (ob::toDFS(tl,2*lvl + 1))
    case List( oa ,None,_*) => (oa::toDFS(tl,2*lvl)) ++ List(None)
    case List( oa , ob ,_*) => (oa :: toDFS(tl, 2*lvl)) ++
                                (ob :: toDFS(tl,2*lvl + 1))
  }
}

现在让我们参数化树，以便我们可以构建Int树、Float树、String树等。

我们还将创建构造函数private，以便仅通过工厂方法完成节点创建。

case class Tree[A] private (value : A
                           ,left  : Option[Tree[A]]
                           ,right : Option[Tree[A]])

剩下的就是提供工厂方法。

object Tree {
  private def BFS2full[A]( . . . //as above 
  private def toDFS[A]( . . . //as above

  def fromDFS[A](dfs :IterableOnce[Option[A]]) :Option[Tree[A]] = {
    val itr = dfs.iterator
    def loop(): Option[Tree[A]] =
      Option.when(itr.hasNext)(itr.next())
            .flatten
            .map(new Tree(_,loop(),loop()))
    loop()
  }
  def fromBFS[A](bfs:IndexedSeq[Option[A]]) :Option[Tree[A]] =
    fromDFS(toDFS(BFS2full(bfs)))
}

测试：

Tree.fromBFS(Vector(Some('A'),None,Some('B'),Some('C'))).get
//res0: Tree[Char] = Tree(A,None,Some(Tree(B,Some(Tree(C,None,None)),None)))
于 2020-06-03T00:04:48.163 回答
1

这是一个基本的解决方案。它不使用惰性 val 或除List、Option和之外的任何数据结构Either。您可能会因此更容易理解，或者因为冗长而更难理解。

我Tree这样定义，只是为了让事情更容易。

sealed trait Tree[+T]
case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object Empty extends Tree[Nothing]

另外，Array[Int]我使用的是 a List[Option[T]]（其中T是makeTree方法的类型参数），而不是 a。Some意味着有一个节点，None就像-1在你的代码中一样。这更惯用，也适用于Int.

做这种广度优先的事情是你需要不断地将输入列表传递给孩子们。首先，您尝试制作左孩子，然后在完成后，您尝试制作右孩子。然后你尝试让左孩子的孩子，然后是右孩子的孩子，然后是他们的孩子，等等。

在不使用的情况下处理此问题的一种方法var是获取包含序列化二叉树的输入列表并查看列表的头部是什么。如果它是 a None，我们可以只返回一个Empty，因为我们知道它是树的末端。但是，如果是 a Some，我们还不能返回树，但我们可以返回另一个函数，该函数接受下一轮输入并返回树。

由于可以返回 2 种不同的类型，因此这些函数的类型为List[Option[T]] => Either[List[Option[T]] => ThisFunctionsType, Tree[T]]. 由于函数可能返回相同类型的另一个函数，我们必须定义一个可以返回自身的新类型：

trait RecFun[T] extends ((List[Option[T]]) => (List[Option[T]], Either[RecFun[T], Tree[T]]))

它的原因List[Option[T]] => (List[Option[T]], Either[RecFun[T], Tree[T]])不仅仅是List[Option[T]] => Either[RecFun[T], Tree[T]]因为如果一个孩子变成了列表中间某处的叶子，我们仍然需要继续，所以返回的元组的第一个元素包含处理后的列表的其余部分。

现在我们可以定义它了。该helper函数是这样的，只要RecFun返回 a Left[RecFun]，它就会继续将剩余的输入传递给该函数。

def makeTree[T](list: List[Option[T]]): Tree[T] = {
  def helper(f: RecFun[T], l: List[Option[T]]): Tree[T] =
    f(l) match {
      case (_, Right(tree)) => tree
      case (next, Left(f))  => helper(f, next)
    }

  list match {
    case Some(x) :: tail => helper(createRec(x), tail)
    case _               => Empty
  }
}

def createRec[T](data: T): RecFun[T] = {
  case None :: Nil | Nil => (Nil, Right(Node(data, Empty, Empty)))
  case Some(l) :: Nil => (Nil, Right(Node(data, Node(l, Empty, Empty), Empty)))
  case lo :: ro :: rest =>
    (rest, (lo, ro) match {
      case (Some(l), Some(r)) =>
        Left(waitForChildren(data, createRec(l), createRec(r)))
      case (Some(l), None) =>
        Left(waitForChild(Node(data, _, Empty), createRec(l)))
      case (None, Some(r)) =>
        Left(waitForChild(Node(data, Empty, _), createRec(r)))
      case (None, None) => Right(Node(data, Empty, Empty))
    })
  }

def waitForChildren[T](data: T, leftF: RecFun[T], rightF: RecFun[T]): RecFun[T] =
  input => {
    val (next, res) = leftF(input)
    res match {
      case Right(tree) =>
        (next, Left(waitForChild(Node(data, tree, _), rightF)))
      case Left(leftF2) => {
        val (next2, res2) = rightF(next)
        (next2, Left(res2 match {
          case Right(tree)   => waitForChild(Node(data, _, tree), leftF2)
          case Left(rightF2) => waitForChildren(data, leftF2, rightF2)
        }))
      }
    }
  }

def waitForChild[T](ctor: Tree[T] => Node[T], f: RecFun[T]): RecFun[T] =
  input => {
    val (next, res) = f(input)
    (next, res match {
      case Right(tree)  => Right(ctor(tree))
      case Left(recFun) => Left(waitForChild(ctor, recFun))
    })
  }

斯卡斯蒂

于 2020-07-18T00:15:48.327 回答