有退货问题的总和的所有路径 [英] All Paths for a Sum with return issues

问题描述

我在寻找求和的所有路径时遇到问题.问题是:

I have a question in finding the all paths for a sum. The question is:

给出一个二叉树和一个数字"S"，找到从根到叶的所有路径，以使每个路径的所有节点值之和等于"S".

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

但是，正确的方法应该是:

However, the correct approach should be:

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

我在这里有一些问题:

1. 为什么在递归语句中不需要 return ?我还对 return 语句如何将输出减少到仅一个感兴趣?

1. Why don't we need a return in the recursion statement? I am also interested in how the return statement reduced the output to only one?

为什么我们不需要 result = find_sum_path(root，target，result，[])?那么更新结果的背后逻辑是什么?

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

我不确定为什么时间复杂度是O(N ^ 2)?

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

上述算法的时间复杂度为O(N ^ 2)，其中"N"是树中节点的总数.这是由于以下事实:我们遍历每个节点一次(将采用O(N))，对于每个叶节点，我们可能必须存储其路径将采用O(N).

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).

谢谢您的帮助.

推荐答案

首先，我想说您已经非常接近解决问题了，并且您做得非常出色.递归是一种功能性遗产，因此将其与功能性样式一起使用可产生最佳效果.这意味着避免诸如突变，变量重新分配和其他副作用之类的事情.这样可以消除许多bug(和头痛)！

First off, I want to say you're very close to solving the problem and you've done a terrific job. Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutations, variable reassignments, and other side effects. This can eliminate many sources of bugs (and headaches)!

为完善您的程序，我们可以从修改 TreeNode 开始，使其在构造时同时接受 left 和 right 参数-

To spruce up your program, we can start by modifying TreeNode to accept both left and right parameters at time of construction -

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

现在我们可以定义两棵树， t1 和 t2 .请注意，我们不会重新分配 root -

Now we can define two trees, t1 and t2. Notice we don't reassign 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 .我们可以使用数学归纳为我们的功能编写简单的案例分析-

Finally we implement find_sum. We can use mathematical induction to write a simple case analysis for our function -

1. 如果输入树 t 为空，则返回空结果
2. (归纳) t 不为空.如果 t.value 与目标 q 相匹配，则找到解决方案；将 t.value 添加到当前的 path 并产生
3. (归纳) t 不为空，并且 t.value 与目标 q 不匹配.将 t.value 添加到当前的 path 和新的子问题 next_q ；解决 t.left 和 t.right 分支上的子问题-

1. if the input tree t is empty, return the empty result
2. (inductive) t is not empty. if t.value matches the target, q, a solution has been found; add t.value to the current path and yield
3. (inductive) t is not empty and t.value does not match the target q. add t.value to the current path and new sub-problem, next_q; solve the sub-problem on t.left and t.right branches -

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 -

Notice how we don't use mutations like .append above. To compute all paths, we can write all_find_sum as the expansion of find_sum -

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

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

And that's it, your program is done :D

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

If you don't want to use a separate generator find_sum, we can expand the generator in place -

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])
      ]

请注意两个变体之间的明显相似性.任何编写良好的程序都可以轻松在两种样式之间进行转换.

Notice the distinct similarity between the two variations. Any well-written program can easily be converted between either style.

这篇关于有退货问题的总和的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！