删除最右边节点时的DFS递归问题

Question

我现在正在研究DFS方法来计算路径的总和。问题陈述是：

给定一棵二叉树和一个数字“S”，找到树中的所有路径，使每条路径的所有节点值之和等于“S”。请注意，路径可以在任何节点开始或结束，但所有路径必须遵循从父节点到子节点（从上到下）的方向。

我的做法是：

def all_sum_path(root, target):
    global count
    count = 0
    find_sum_path(root, target, [])
    return count

def find_sum_path(root, target, allPath):
    global count
    if not root:
        return 0
    # add a space for current node
    allPath.append(0)
    # add current node values to all path
    allPath = [i+root.value for i in allPath]
    print(allPath)
    # check if current path == target
    for j in allPath:
        if j == target:
            count += 1
    # recursive
    find_sum_path(root.left, target, allPath)
    find_sum_path(root.right, target, allPath)
    # remove the current path
    print('after', allPath)
    allPath.pop()
    print('after pop', allPath)

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

def main():
    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, 11))

main()

带返回：

[1]
[8, 7]
[14, 13, 6]
after [14, 13, 6]
after pop [14, 13]
[13, 12, 5, 5]
after [13, 12, 5, 5]
after pop [13, 12, 5]
after [8, 7, 0, 0]
after pop [8, 7, 0]
[10, 9, 9]
[12, 11, 11, 2]
after [12, 11, 11, 2]
after pop [12, 11, 11]
[13, 12, 12, 3, 3]
after [13, 12, 12, 3, 3]
after pop [13, 12, 12, 3]
after [10, 9, 9, 0, 0]
after pop [10, 9, 9, 0]
after [1, 0, 0]
after pop [1, 0]
4

我认为问题在于我没有成功删除列表中最右边的节点。然后我更新了我的代码如下，删除了allPath最右边的节点，并创建了一个名为newAllPath的新列表来记录已经加上当前节点值的节点。

def all_sum_path(root, target):
    global count
    count = 0
    find_sum_path(root, target, [])
    return count

def find_sum_path(root, target, allPath):
    global count
    if not root:
        return 0
    # add a space for current node
    allPath.append(0)
    # add current node values to all path
    newAllPath = [i+root.value for i in allPath]
    print(allPath, newAllPath)
    # check if current path == target
    for j in newAllPath:
        if j == target:
            count += 1
    # recursive
    find_sum_path(root.left, target, newAllPath)
    find_sum_path(root.right, target, newAllPath)
    # remove the current path
    print('after', allPath, newAllPath)
    allPath.pop()
    print('after pop', allPath, newAllPath)

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(6)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(2)
    root.right.right = TreeNode(3)

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

main()

带返回：

[0] [1]
[1, 0] [8, 7]
[8, 7, 0] [14, 13, 6]
after [8, 7, 0] [14, 13, 6]
after pop [8, 7] [14, 13, 6]
[8, 7, 0] [13, 12, 5]
after [8, 7, 0] [13, 12, 5]
after pop [8, 7] [13, 12, 5]
after [1, 0] [8, 7]
after pop [1] [8, 7]
[1, 0] [10, 9]
[10, 9, 0] [12, 11, 2]
after [10, 9, 0] [12, 11, 2]
after pop [10, 9] [12, 11, 2]
[10, 9, 0] [13, 12, 3]
after [10, 9, 0] [13, 12, 3]
after pop [10, 9] [13, 12, 3]
after [1, 0] [10, 9]
after pop [1] [10, 9]
after [0] [1]
after pop [] [1]
3

我不确定为什么在第一种方法中无法成功删除最右边的节点。然而，在我的第二种方法中，一旦我删除了allPath中最右边的节点，它也会删除newAllPath中的节点。

谢谢你的帮助。我很困惑，一整天都被困在这里。

Answer 1

功能原理

这是一个非常重要的问题，我不会尝试调试您的程序，因为它违背了递归的使用方式。重申一下，递归是一种函数遗产，因此将其与函数风格结合使用会产生最好的结果。这意味着避免-

• 突变，如. append，=1，. pop
• 重新分配像左=...，右=...，allPath=...
• 全局像计数
• 其他副作用，如print

分解

试图将任务的所有关注点打包到一个函数中是个坏主意。把问题分解成不同的部分有很多好处-

• 更小的函数更容易读、写、测试和调试
• 单一用途的功能更易于重用

首先，我们将使用我们在之前的Q中已经写过的find_sum

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

使用find_sum我们可以轻松编写all_sum-

def all_sum(t, q):
  for n in traverse(t):
    yield from find_sum(n, q)

这需要我们编写一个通用的遍历-

def traverse(t):
  if not t:
    return
  else:
    yield from traverse(t.left)
    yield t
    yield from traverse(t.right)

让我们看看它在样本树上的工作情况-

               12
             /    \
            /      \
           7        1
          / \      / \
         4   3    10  5
            /    /
           1    1

我们使用您的TreeNode构造函数来表示它-

t1 = TreeNode \
  ( 12
  , TreeNode(7, TreeNode(4), TreeNode(3, TreeNode(1)))
  , TreeNode(1, TreeNode(10, TreeNode(1)), TreeNode(5))
  )

print(list(all_sum(t1, 11)))

[[7, 4], [7, 3, 1], [10, 1], [1, 10]]

计算所有的金额

如果唯一的目标是计算总和，我们可以编写count_all_sum作为all_sum-

def count_all_sum (t, q):
  return len(list(all_sum(t, q)))

Answer 2

除非你的树深度超过1000个节点，否则你可以使用递归来获得更简单的代码：

def findSums(node,target):
    if not node : return
    if node.value == target: yield [node.value]           # target reached, return path
    for child in (node.left,node.right):                  # traverse tree DFS
        yield from findSums(child,target)                 # paths skipping this node 
        for subPath in findSums(child,target-node.value): # paths with remainder
            yield [node.value]+subPath                    # value + sub-path

for sp in findSums(root,11):
    print(sp)

# [7, 4]
# [1, 10]

要打印二叉树，请参阅以下内容：https://stackoverflow.com/a/49844237/5237560