Путь решения Sum II в Scala - PullRequest
Новая
       6

Путь решения Sum II в Scala

1 голос
/ 15 марта 2020

Я новичок в Scala и пытаюсь найти Path Sum II на leetcode с Scala, который гласит: По заданному двоичному дереву и сумме найти все root пути к листу, где сумма каждого пути равна заданной сумме.

Примечание: лист - это узел без дочерних элементов.

Я придумал это решение, которое до сих пор работало для деревьев. только с положительными целыми числами, но не работает на деревьях, включая отрицательные целые числа, и после нескольких часов попыток я решил обратиться к вам за помощью. 

/**
* 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
     }
   }
 }  
}

Я понимаю, что с отрицательными числами можно получить сумму и не быть на узле root, однако я не уверен, как добавить эту проверку, возможно, из-за моей реализации. Буду признателен, если кто-нибудь сможет объяснить мне, как добавить это ограничение или какие-либо комментарии о моем подходе.

Ответы [ 2 ]

1 голос
/ 16 марта 2020

Вот мое решение: 

def pathSum(root: TreeNode, sum: Int): List[List[Int]] ={
    if(root == null) Nil
    else if(root.right == null && root.left == null) if(sum == root.value) List(List(sum)) else Nil
    else (pathSum(root.left, sum-root.value) ++ pathSum(root.right, sum-root.value)).map(root.value::_)
}

Время выполнения: 564 мс, быстрее, чем 92,86% от Scala онлайн-заявок на Path Sum II. Использование памяти: 53,9 МБ, менее 100,00% от Scala онлайн-заявок на Path Sum II.

1 голос
/ 15 марта 2020

Прошло пару лет с тех пор, как я решил этот. Рассматривая старый код, кажется, что идея состоит в том, чтобы вычитать 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)}
}
...