Блог

Хороший день. Могу ли я задать вопрос о том, когда использовать return в рекурсии. Я в основном хочу использовать рекурсию для решения следующего вопроса:

Учитывая корень двоичного дерева и целочисленное целочисленное число, верните все пути от корня к листу, где сумма значений узлов в пути равна целевому числу. Каждый путь должен быть возвращен в виде списка значений узлов, а не ссылок на узлы. Путь от корня к листу-это путь, начинающийся от корня и заканчивающийся в любом конечном узле. Лист — это узел без дочерних элементов. Входные данные: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Выход: [[5,4,11,2],[5,8,4,5]]

Пояснение: Есть два пути, сумма которых равна targetSum:

5 4 11 2 = 22

5 8 4 5 = 22

Вот мое кодовое решение

 def pathSum(self, root: Optional[TreeNode], targetSum: int) -gt; List[List[int]]:  res = []  def helper(node, target, cur):  if not node:  return  cur.append(node.val)  if target == node.val and not node.left and not node.right:  res.append(list(cur))  print(res)  return # why can't we put return here  helper(node.left, target - node.val, cur)  helper(node.right, target- node.val, cur)  cur.pop()  helper(root, targetSum, [])  return res  

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

Этот код использует метод обратного отслеживания, чтобы найти все решения (пути) проблемы.

Когда вы возвращаетесь рано, вы лишаете решение возможности доступа к pop последнему элементу, который вы добавили в свой текущий список. Удалите это раннее возвращение и позвольте алгоритму позаботиться о возврате в базовом случае, вернитесь в рекурсивный стек и pop последний элемент из текущего пути, как показано ниже:

 def pathSum(self, root: Optional[TreeNode], targetSum: int) -gt; List[List[int]]:  res = []  def helper(node, target, cur):  if not node:  return  cur.append(node.val)  if target == node.val and not node.left and not node.right:  res.append(list(cur))  print(res)  # when your code comes out of this if condition  # node.left and node.right will be None  # it calls the below functions and they return  # and then it will pop the last element  helper(node.left, target - node.val, cur)  helper(node.right, target- node.val, cur)  cur.pop()  helper(root, targetSum, [])  return res