有返回问题的总和的所有路径

2022-01-19 00:00:00 python 递归 return binary-tree

问题描述

我有一个问题是要找到总和的所有路径.问题是:

<块引用>

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

我的递归方法是:

def all_sum_path(root, target):结果 = []find_sum_path(根，目标，结果，[])返回结果def find_sum_path(根，目标，结果，新路径):如果不是根:返回无new_path.append(root.value)diff = 目标 - root.value如果不是 root.left 而不是 root.right 并且 diff == 0:# 复制列表的值而不是引用结果.附加(列表(新路径))如果root.left:return find_sum_path(root.left, diff, result, new_path)如果root.right:return find_sum_path(root.right, diff, result, new_path)删除新路径[-1]类树节点():def __init__(self, _value):self.value = _valueself.left，self.right，self.next = 无，无，无定义主():根 = 树节点(1)root.left = 树节点(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)打印(all_sum_path(根，12))根 = 树节点(12)root.left = 树节点(7)root.right = 树节点(1)root.left.left = TreeNode(4)root.right.left = TreeNode(10)root.right.right = TreeNode(5)打印(all_sum_path(根，23))主要的()

输出是:

[[1, 7, 4]][[12, 7, 4]]进程以退出代码 0 结束

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

def all_sum_path(root, target):结果 = []find_sum_path(根，目标，结果，[])返回结果def find_sum_path(根，目标，结果，新路径):如果不是根:返回无new_path.append(root.value)diff = 目标 - root.value如果不是 root.left 而不是 root.right 并且 diff == 0:# 复制列表的值而不是引用结果.附加(列表(新路径))如果root.left:find_sum_path(root.left, diff, result, new_path)如果root.right:find_sum_path(root.right, diff, result, new_path)删除新路径[-1]类树节点():def __init__(self, _value):self.value = _valueself.left，self.right，self.next = 无，无，无定义主():根 = 树节点(1)root.left = 树节点(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)打印(all_sum_path(根，12))根 = 树节点(12)root.left = 树节点(7)root.right = 树节点(1)root.left.left = TreeNode(4)root.right.left = TreeNode(10)root.right.right = TreeNode(5)打印(all_sum_path(根，23))主要的()

有输出:

[[1, 7, 4], [1, 9, 2]][[12, 7, 4], [12, 1, 10]]进程以退出代码 0 结束

我在这里有一些问题:

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

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

  3. 不知道为什么时间复杂度是O(N^2)?

<块引用>

上述算法的时间复杂度为O(N^2)，其中‘N’是树中节点的总数.这是因为我们遍历每个节点一次(这将花费 O(N))，并且对于每个叶节点，我们可能必须存储它的路径，这将花费 O(N).

提前感谢您的帮助.

解决方案

首先，我想说你已经非常接近解决问题了，你已经完成了一项了不起的工作.递归是一种函数式遗产，因此将其与函数式风格一起使用会产生最佳结果.这意味着要避免诸如突变、变量重新分配和其他副作用之类的事情.这可以消除许多错误来源(和令人头疼的问题)！

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

类 TreeNode():def __init__(self, value, left=None, right=None):自我价值=价值self.left = 左self.right = 对

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

def main():t1 = 树节点 ( 1, 树节点 (7, 树节点 (4), 树节点 (5)), 树节点 (9, 树节点 (2), 树节点 (7)))t2 = 树节点 ( 12，树节点(7，树节点(4)，无), 树节点 (1, 树节点 (10), 树节点 (5)))打印(all_sum_path(t1，12))打印(all_sum_path(t2，23))主要的()

预期的输出是 -

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

最后我们实现了find_sum.我们可以使用数学归纳法为我们的函数写一个简单的案例分析-

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

def find_sum (t, q, path = []):如果不是 t:返回 # (1)elif t.value == q:yield [*path, t.value] # (2)别的:next_q = q - t.value # (3)next_path = [*路径，t.value]从 find_sum(t.left, next_q, next_path) 中产生来自 find_sum(t.right, next_q, next_path)

请注意我们如何不使用上面的 .append 之类的突变.为了计算 all 路径，我们可以将 all_find_sum 写成 find_sum -

的展开

def all_sum_path (t, q):返回列表(find_sum(t，q))

就是这样，你的程序已经完成了:D

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

def all_sum_path (t, q, path = []):如果不是 t:返回 []elif t.value == q:返回 [[*path, t.value]]别的:返回 [ *all_sum_path(t.left, q - t.value, [*path, t.value]), *all_sum_path(t.right, q - t.value, [*path, t.value])]

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

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

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

My approach with recursion is:

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

and the output is:

[[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()

With output:

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

Process finished with exit code 0

I have a some questions here:

  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?

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

  3. I am not sure why the time complexity is 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).

Thanks for your help in advance.

解决方案

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

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

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

The expected output is -

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

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

  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)

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

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

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.

相关文章