为以下问题编写了一个不必要的复杂解决方案:
给定一个二叉树和一个和,确定树是否有
根到叶路径,以便将路径上的所有值相加
等于给定的和。
不管怎样,我在试着调试出了什么问题。我使用了一个命名元组,这样我就可以同时跟踪数字是否已找到以及运行和,但是运行和的增量似乎永远不会超过零。但是,在任何给定的叶节点上,运行和将是叶节点的值,在下一次迭代中,运行和应乘以当前运行和。有人知道我的“信仰的递归飞跃”有什么问题吗?
def root_to_leaf(target_sum, tree):
NodeData = collections.namedtuple('NodeData', ['running_sum', 'num_found'])
def root_to_leaf_helper(node, node_data):
if not node:
return NodeData(0, False)
if node_data.num_found:
return NodeData(target_sum, True)
left_check = root_to_leaf_helper(node.left, node_data)
if left_check.num_found:
return NodeData(target_sum, True)
right_check = root_to_leaf_helper(node.right, node_data)
if right_check.num_found:
return NodeData(target_sum, True)
new_running_sum = node.val + node_data.running_sum
return NodeData(new_running_sum, new_running_sum == target_sum)
return root_to_leaf_helper(tree, NodeData(0, False)).num_found
编辑:我意识到这实际上只是检查任何路径(不是以leaf结尾)是否具有正确的值,但我的问题仍然是理解为什么运行和没有正确地递增。
最佳答案
可以保留路径的运行列表作为递归函数/方法签名的一部分,并使用生成器在左右节点上调用函数/方法生成器将使您能够找到从起始节点延伸的路径为了简单起见,我将解决方案实现为类方法:
class Tree:
def __init__(self, *args):
self.__dict__ = dict(zip(['value', 'left', 'right'], args))
def get_sums(self, current = []):
if self.left is None:
yield current + [self.value]
else:
yield from self.left.get_sums(current+[self.value])
if self.right is None:
yield current+[self.value]
else:
yield from self.right.get_sums(current+[self.value])
tree = Tree(4, Tree(10, Tree(4, Tree(7, None, None), Tree(6, None, None)), Tree(12, None, None)), Tree(5, Tree(6, None, Tree(11, None, None)), None))
paths = list(tree.get_sums())
new_paths = [a for i, a in enumerate(paths) if a not in paths[:i]]
final_path = [i for i in paths if sum(i) == 15]
输出:
[[4, 5, 6]]
关于python - 根到叶算法错误,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/50532690/