具有 return 个问题的求和的所有路径

Question

我在查找总和的所有路径时遇到问题。问题是：

Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’.

我的递归方法是：

def all_sum_path(root, target):
    result = []
    find_sum_path(root, target, result, [])
    return result

def find_sum_path(root, target, result, new_path):
    if not root:
        return None
    new_path.append(root.value)
    diff = target - root.value
    if not root.left and not root.right and diff == 0:
        # copy the value of the list rather than a reference
        result.append(list(new_path))
    if root.left:
        return find_sum_path(root.left, diff, result, new_path)
    if root.right:
        return find_sum_path(root.right, diff, result, new_path)
    del new_path[-1]


class TreeNode():
    def __init__(self, _value):
        self.value = _value
        self.left, self.right, self.next = None, None, None

def main():
    root = TreeNode(1)
    root.left = TreeNode(7)
    root.right = TreeNode(9)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(2)
    root.right.right = TreeNode(7)

    print(all_sum_path(root, 12))

    root = TreeNode(12)
    root.left = TreeNode(7)
    root.right = TreeNode(1)
    root.left.left = TreeNode(4)
    root.right.left = TreeNode(10)
    root.right.right = TreeNode(5)

    print(all_sum_path(root, 23))

main()

输出为：

[[1, 7, 4]]
[[12, 7, 4]]

Process finished with exit code 0

但是，正确的做法应该是：

def all_sum_path(root, target):
    result = []
    find_sum_path(root, target, result, [])
    return result

def find_sum_path(root, target, result, new_path):
    if not root:
        return None
    new_path.append(root.value)
    diff = target - root.value
    if not root.left and not root.right and diff == 0:
        # copy the value of the list rather than a reference
        result.append(list(new_path))
    if root.left:
        find_sum_path(root.left, diff, result, new_path)
    if root.right:
        find_sum_path(root.right, diff, result, new_path)
    del new_path[-1]


class TreeNode():
    def __init__(self, _value):
        self.value = _value
        self.left, self.right, self.next = None, None, None

def main():
    root = TreeNode(1)
    root.left = TreeNode(7)
    root.right = TreeNode(9)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(2)
    root.right.right = TreeNode(7)

    print(all_sum_path(root, 12))

    root = TreeNode(12)
    root.left = TreeNode(7)
    root.right = TreeNode(1)
    root.left.left = TreeNode(4)
    root.right.left = TreeNode(10)
    root.right.right = TreeNode(5)

    print(all_sum_path(root, 23))

main()

输出：

[[1, 7, 4], [1, 9, 2]]
[[12, 7, 4], [12, 1, 10]]

Process finished with exit code 0

我有一些问题：

为什么我们在递归语句中不需要return？我也对 return 语句如何将输出减少到只有一个感兴趣？
为什么我们不需要 result = find_sum_path(root, target, result, [])？那么更新结果的逻辑是什么？
不知道为什么时间复杂度是O(N^2)？

The time complexity of the above algorithm is O(N^2), where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once (which will take O(N)), and for every leaf node we might have to store its path which will take O(N).

提前感谢您的帮助。

Answer 1

Why don't we need a return in the recursion statement?

Why don't we need the result = find_sum_path(root, target, result, [])? Then what is the logic behind to update the results?

result 列表（以及 new_path 列表）通过引用（或者更确切地说是通过赋值，参见 what does it mean by 'passed by assignment'?）通过递归堆栈传递，这意味着 result 变量始终指向内存中与它在 all_sum_path 中初始化时相同的位置（只要它没有被重新分配）并且您可以根据需要在适当的位置改变它。

I am also interested in how the return statement reduced the output to only one?

当您在解决方案中使用 return 时，当左子树完成时，您将完全放弃探索节点的右子树。

if root.left: 
    return find_sum_path(root.left, diff, result, new_path)
# -- unreachable code if `root.left` is not `None` --
if root.right:
    return find_sum_path(root.right, diff, result, new_path)

I am not sure why the time complexity is O(N^2)?

if not root.left and not root.right and diff == 0:
    # copy the value of the list rather than a reference
    result.append(list(new_path))

这部分代码正在制作 new_path 的完整副本以将其附加到 result。以介于高度不平衡和完全平衡之间的二叉树为例，所有节点的值为 0 并且 S 也为 0。在这种情况下，您将使 L（叶节点数) new_path 的副本，每个包含最多 H 个元素（树的高度）所以 O(L * H) ~ O(N^2)

所以最坏情况可能的时间复杂度肯定不是线性 O(N) 但也不完全是 O(N^2)。

Answer 2

首先，我想说您已经非常接近解决问题，而且您做得非常出色。递归是一种函数式继承，因此将它与函数式风格一起使用会产生最好的结果。这意味着要避免诸如突变、变量重新分配和其他副作用之类的事情。这可以消除许多错误来源（和令人头疼的问题）！

为了美化你的程序，我们可以从修改 TreeNode 开始，在构造时接受 left 和 right 参数 -

class TreeNode():
  def __init__(self, value, left=None, right=None):
    self.value = value
    self.left = left
    self.right = right

现在我们可以定义两棵树，t1和t2。注意我们没有重新分配 root -

def main():
  t1 = TreeNode \
    ( 1
    , TreeNode(7, TreeNode(4), TreeNode(5))
    , TreeNode(9, TreeNode(2), TreeNode(7))
    )
    
  t2 = TreeNode \
    ( 12
    , TreeNode(7, TreeNode(4), None)
    , TreeNode(1, TreeNode(10), TreeNode(5))
    )

  print(all_sum_path(t1, 12))
  print(all_sum_path(t2, 23))

main()

预期输出为 -

[[1, 7, 4], [1, 9, 2]]
[[12, 7, 4], [12, 1, 10]]

我们终于实现了 find_sum。我们可以使用mathematical induction为我们的函数写一个简单的案例分析-

如果输入树 t 为空，return 为空结果
（归纳）t 不是空。如果 t.value 与目标 q 匹配，则已找到解决方案；将 t.value 添加到当前 path 并产生
（归纳）t 不为空并且 t.value 不匹配目标 q。将 t.value 添加到当前的 path 和新的子问题 next_q；解决 t.left 和 t.right 分支上的子问题 -

def find_sum (t, q, path = []):
  if not t:
    return                        # (1)
  elif t.value == q:
    yield [*path, t.value]        # (2)
  else:
    next_q = q - t.value          # (3)
    next_path = [*path, t.value]
    yield from find_sum(t.left, next_q, next_path)
    yield from find_sum(t.right, next_q, next_path)

请注意我们如何不使用像上面 .append 这样的突变。要计算 all 路径，我们可以将 all_find_sum 写为 find_sum -

的扩展

def all_sum_path (t, q):
  return list(find_sum(t, q))

就是这样，您的程序已完成:D

如果你不想使用单独的生成器find_sum，我们可以就地扩展生成器-

def all_sum_path (t, q, path = []):
  if not t:
    return []
  elif t.value == q:
    return [[*path, t.value]]
  else:
    return \
      [ *all_sum_path(t.left, q - t.value, [*path, t.value])
      , *all_sum_path(t.right, q - t.value, [*path, t.value])
      ]

请注意这两种变体之间明显的相似之处。任何编写良好的程序都可以在两种风格之间轻松转换。

具有 return 个问题的求和的所有路径

All Paths for a Sum with return issues

python

recursion

binary-tree

return