时间戳

首页 > 解决方案 > 在 Scala 中求解路径总和 II

scala - 在 Scala 中求解路径总和 II

问题描述

我是 Scala 的初学者，我正在尝试使用 Scala 解决 leetcode 上的Path Sum II，它指出：给定一个二叉树和一个总和，找到所有从根到叶的路径，其中每个路径的总和等于给定的总和。

注意：叶子是没有子节点的节点。

我想出了这个解决方案，到目前为止它只适用于具有正整数的树，但在包括负整数的树上却失败了，经过数小时的尝试，我决定寻求你的帮助。

/**
* Definition for a binary tree node.
* class TreeNode(var _value: Int) {
*   var value: Int = _value
*   var left: TreeNode = null
*   var right: TreeNode = null
* }
*/
object Solution {
 def pathSum(root: TreeNode, sum: Int): List[List[Int]] = {
   if (root == null) List()
   else if(root.value == sum && (root.right == null && root.left == null)) List(List(root.value))
   else
     pathSumhelper2(pathSumhelper(root.left, sum, root.value, root.value::Nil, Nil) :::
       pathSumhelper(root.right, sum, root.value, root.value::Nil, Nil))
 }

 def pathSumhelper2(l1: List[List[Int]]): List[List[Int]] = l1 match {
   case Nil => l1
   case x :: y => x.reverse :: pathSumhelper2(y)
 }


 def pathSumhelper(root: TreeNode, sum: Int, accumSum: Int, currentList: List[Int], result: List[List[Int]]): List[List[Int]] = {

   if (root==null) result
   else if (accumSum+root.value==sum) (root.right,root.left) match {
   case(null,null) => root.value :: currentList match { case x => x :: result}
       case(_,_) => result
   }
 else {
     root.value :: currentList match {
       case x => (pathSumhelper(root.left, sum, root.value + accumSum, x, result) :::
         pathSumhelper(root.right, sum, root.value + accumSum, x, result)).distinct
     }
   }
 }  
}

我知道使用负数可以获得总和而不是在根节点，但是我不确定如何添加此检查，可能是由于我的实现。如果有人能告诉我如何添加这个约束或对我的方法有任何评论，我将不胜感激。

标签： scalafunctional-programmingbinary-tree

解决方案

我解决这个问题已经有几年了。回顾旧代码，它的想法似乎是每次递归都减去value，sum这样当我们到达叶节点时，我们只需测试sum == value.

def pathSum(root:TreeNode, sum:Int, path:List[Int]=List()):List[List[Int]] = {
  if (root == null) List()
  else if (root.left == null && root.right == null)
    if (sum == root.value) List((root.value :: path).reverse)
    else List[List[Int]]()
  else
    Option(root.left).fold(List[List[Int]]()) {tn =>
      pathSum(tn, sum-root.value, root.value::path)} :::
      Option(root.right).fold(List[List[Int]]()) {tn =>
        pathSum(tn, sum-root.value, root.value::path)}
}

推荐阅读