找出树中总和为 S 的所有路径
Find all paths in a tree that sum to S
给定一棵二叉树和一个数字“S”，找到树中的所有路径，使得每条路径的所有节点值的总和等于“S”。请注意，路径可以在任何节点开始或结束，但所有路径必须遵循从父到子（从上到下）的方向。
这是我找到的一个答案，我确实理解它是如何工作的，但我最初想到的是我想要实现的不同的东西，但我很难弄明白。
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_paths(root, S):
return count_paths_recursive(root, S, [])
def count_paths_recursive(currentNode, S, currentPath):
if currentNode is None:
return 0
# add the current node to the path
currentPath.append(currentNode.val)
pathCount, pathSum = 0, 0
# find the sums of all sub-paths in the current path list
for i in range(len(currentPath)-1, -1, -1):
pathSum += currentPath[i]
# if the sum of any sub-path is equal to 'S' we increment our path count.
if pathSum == S:
pathCount += 1
# traverse the left sub-tree
pathCount += count_paths_recursive(currentNode.left, S, currentPath)
# traverse the right sub-tree
pathCount += count_paths_recursive(currentNode.right, S, currentPath)
# remove the current node from the path to backtrack
# we need to remove the current node while we are going up the recursive call stack
del currentPath[-1]
return pathCount
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("Tree has paths: " + str(count_paths(root, 11)))
main()
我想要做的是 DFS 但我不想保留列表，而是只想跟踪我的当前节点并有一个起始节点以及我保存在内存中例如，
为了树...
1
/ \
7 9
/ \ |\
6 5 2 3
如果我想找到所有加起来为 12 且不必从根开始或在叶结束的路径，那么我的计划是跟踪我的初始起始节点和我所在的当前节点.
为了保持这个 post 简短，我跳过了第一个路径，因为
1 -> 7
1 -> 7 -> 6
7 -> 6
加起来是 12。
从下一条可能的路径开始让我们从根节点开始...
我们在 1 并且 1 小于 12 所以我们移动到下一个节点 7 并且 1 + 7 是 8 并且 8 小于 12 所以我们继续到下一个节点 5 并且 8 + 5 是 13 .
13 大于 12 我立即知道我需要从头开始收缩路径，在本例中是值为 1 的节点。收缩时我们需要确保从 运行 总和中减去我们有我们要放手的节点的价值。所以 13 - 1 是 12，我们找到了一条加起来等于目标总和的路径。对其余路径一遍又一遍地继续此算法
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_paths(root, S):
return count_paths_helper(root, S, root, 0, 0)
def count_paths_helper(current_node, S, start, running_sum, num_paths):
if current_node is None:
return 0
running_sum += current_node.val
# Found a path
if running_sum == S:
return 1
# shrink the path starting from the beginning
if running_sum > S:
# if the beginning of the path is also equal to the end of the path continue on our path
# and get rid of the running sum we currently have
if start == current_node:
num_paths += count_paths_helper(current_node.left, S, start, running_sum - start.val, num_paths)
num_paths += count_paths_helper(current_node.right, S, start, running_sum - start.val, num_paths)
# shrink the path starting from the beginning moving to the left
if start.left:
num_paths += count_paths_helper(current_node, S, start.left, running_sum - start.val, num_paths)
# shrink the path starting from the beginning moving to the right
if start.right:
num_paths += count_paths_helper(current_node, S, start.right, running_sum - start.val, num_paths)
# if we are on a path that has not exceeded the target and not equal to the target sum
# continue on our path
else:
num_paths += count_paths_helper(current_node.left, S, start, running_sum, num_paths)
num_paths += count_paths_helper(current_node.right, S, start, running_sum, num_paths)
return num_paths
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("Tree has paths: " + str(count_paths(root, 11)))
main()
这行不通，我真的不明白如何实现它。
一些问题：
- 您的算法想法只有在节点的值为非负时才有效。
num_paths 被错误地累积：你将它作为参数传递给递归调用，执行将 添加 和 return 增加的结果，之后您 添加 它到调用者的 num_paths 值。这是错误的，因为它总是会向 num_paths 添加一个至少与 num_paths 一样大的值，使其在每次此类分配时加倍。您可以省略函数参数，让函数的每次执行都从 0 和 return 开始。- 在
if start == current_node: 的情况下，你应该传递 start.left 或 start.right 作为第三个参数而不是 start，因为你用 start.val 减少了总和.
if start == current_node: 应该有一个对应的 else 块，因为当前代码的其余部分仍然会在这个条件为真时执行，从而递归调用将得到两个错误的节点顺序，代表一种“负”路径。
这里更正：
def count_paths(root, S):
return count_paths_helper(root, S, root, 0)
def count_paths_helper(current_node, S, start, running_sum):
if current_node is None:
return 0
running_sum += current_node.val
# Found a path
if running_sum == S:
return 1
num_paths = 0
# shrink the path starting from the beginning
if running_sum > S:
# if the beginning of the path is also equal to the end of the path continue on our path
# and get rid of the running sum we currently have
if start == current_node:
num_paths += count_paths_helper(current_node.left, S, start.left, running_sum - start.val)
num_paths += count_paths_helper(current_node.right, S, start.right, running_sum - start.val)
else:
# shrink the path starting from the beginning moving to the left
num_paths += count_paths_helper(current_node, S, start.left, running_sum - start.val)
# shrink the path starting from the beginning moving to the right
num_paths += count_paths_helper(current_node, S, start.right, running_sum - start.val)
# if we are on a path that has not exceeded the target and not equal to the target sum
# continue on our path
else:
num_paths += count_paths_helper(current_node.left, S, start, running_sum)
num_paths += count_paths_helper(current_node.right, S, start, running_sum)
return num_paths
给定一棵二叉树和一个数字“S”，找到树中的所有路径，使得每条路径的所有节点值的总和等于“S”。请注意，路径可以在任何节点开始或结束，但所有路径必须遵循从父到子（从上到下）的方向。
这是我找到的一个答案，我确实理解它是如何工作的，但我最初想到的是我想要实现的不同的东西，但我很难弄明白。
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_paths(root, S):
return count_paths_recursive(root, S, [])
def count_paths_recursive(currentNode, S, currentPath):
if currentNode is None:
return 0
# add the current node to the path
currentPath.append(currentNode.val)
pathCount, pathSum = 0, 0
# find the sums of all sub-paths in the current path list
for i in range(len(currentPath)-1, -1, -1):
pathSum += currentPath[i]
# if the sum of any sub-path is equal to 'S' we increment our path count.
if pathSum == S:
pathCount += 1
# traverse the left sub-tree
pathCount += count_paths_recursive(currentNode.left, S, currentPath)
# traverse the right sub-tree
pathCount += count_paths_recursive(currentNode.right, S, currentPath)
# remove the current node from the path to backtrack
# we need to remove the current node while we are going up the recursive call stack
del currentPath[-1]
return pathCount
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("Tree has paths: " + str(count_paths(root, 11)))
main()
我想要做的是 DFS 但我不想保留列表，而是只想跟踪我的当前节点并有一个起始节点以及我保存在内存中例如，
为了树...
1
/ \
7 9
/ \ |\
6 5 2 3
如果我想找到所有加起来为 12 且不必从根开始或在叶结束的路径，那么我的计划是跟踪我的初始起始节点和我所在的当前节点.
为了保持这个 post 简短，我跳过了第一个路径，因为
1 -> 7
1 -> 7 -> 6
7 -> 6
加起来是 12。
从下一条可能的路径开始让我们从根节点开始...
我们在 1 并且 1 小于 12 所以我们移动到下一个节点 7 并且 1 + 7 是 8 并且 8 小于 12 所以我们继续到下一个节点 5 并且 8 + 5 是 13 .
13 大于 12 我立即知道我需要从头开始收缩路径，在本例中是值为 1 的节点。收缩时我们需要确保从 运行 总和中减去我们有我们要放手的节点的价值。所以 13 - 1 是 12，我们找到了一条加起来等于目标总和的路径。对其余路径一遍又一遍地继续此算法
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_paths(root, S):
return count_paths_helper(root, S, root, 0, 0)
def count_paths_helper(current_node, S, start, running_sum, num_paths):
if current_node is None:
return 0
running_sum += current_node.val
# Found a path
if running_sum == S:
return 1
# shrink the path starting from the beginning
if running_sum > S:
# if the beginning of the path is also equal to the end of the path continue on our path
# and get rid of the running sum we currently have
if start == current_node:
num_paths += count_paths_helper(current_node.left, S, start, running_sum - start.val, num_paths)
num_paths += count_paths_helper(current_node.right, S, start, running_sum - start.val, num_paths)
# shrink the path starting from the beginning moving to the left
if start.left:
num_paths += count_paths_helper(current_node, S, start.left, running_sum - start.val, num_paths)
# shrink the path starting from the beginning moving to the right
if start.right:
num_paths += count_paths_helper(current_node, S, start.right, running_sum - start.val, num_paths)
# if we are on a path that has not exceeded the target and not equal to the target sum
# continue on our path
else:
num_paths += count_paths_helper(current_node.left, S, start, running_sum, num_paths)
num_paths += count_paths_helper(current_node.right, S, start, running_sum, num_paths)
return num_paths
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("Tree has paths: " + str(count_paths(root, 11)))
main()
这行不通，我真的不明白如何实现它。
一些问题：
- 您的算法想法只有在节点的值为非负时才有效。
num_paths被错误地累积：你将它作为参数传递给递归调用，执行将 添加 和 return 增加的结果，之后您 添加 它到调用者的num_paths值。这是错误的，因为它总是会向num_paths添加一个至少与num_paths一样大的值，使其在每次此类分配时加倍。您可以省略函数参数，让函数的每次执行都从 0 和 return 开始。- 在
if start == current_node:的情况下，你应该传递start.left或start.right作为第三个参数而不是start，因为你用start.val减少了总和. if start == current_node:应该有一个对应的else块，因为当前代码的其余部分仍然会在这个条件为真时执行，从而递归调用将得到两个错误的节点顺序，代表一种“负”路径。
这里更正：
def count_paths(root, S):
return count_paths_helper(root, S, root, 0)
def count_paths_helper(current_node, S, start, running_sum):
if current_node is None:
return 0
running_sum += current_node.val
# Found a path
if running_sum == S:
return 1
num_paths = 0
# shrink the path starting from the beginning
if running_sum > S:
# if the beginning of the path is also equal to the end of the path continue on our path
# and get rid of the running sum we currently have
if start == current_node:
num_paths += count_paths_helper(current_node.left, S, start.left, running_sum - start.val)
num_paths += count_paths_helper(current_node.right, S, start.right, running_sum - start.val)
else:
# shrink the path starting from the beginning moving to the left
num_paths += count_paths_helper(current_node, S, start.left, running_sum - start.val)
# shrink the path starting from the beginning moving to the right
num_paths += count_paths_helper(current_node, S, start.right, running_sum - start.val)
# if we are on a path that has not exceeded the target and not equal to the target sum
# continue on our path
else:
num_paths += count_paths_helper(current_node.left, S, start, running_sum)
num_paths += count_paths_helper(current_node.right, S, start, running_sum)
return num_paths