为以下问题编写了一个不必要的复杂解决方案:
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
无论如何,我正在尝试调试这里出了什么问题。我使用了一个命名的元组,这样我就可以跟踪是否找到了数字和运行总和,但看起来运行总和永远不会超过零。但是,在任何给定的叶节点,运行总和将是叶节点的值,并且在下一次迭代中,运行总和应增加当前运行总和。任何人都知道我的“递归信仰飞跃”有什么问题吗?
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
编辑:我意识到这实际上只是检查任何路径(不以叶结束)是否具有正确的值,但我的问题仍然在于理解为什么运行总和没有正确递增。
最佳答案
我认为您需要清楚地考虑信息是沿着树向下流动(从根到叶)还是向上流动(从叶到根)。看起来 root_to_leaf_helper
的 node_data
参数在树的顶部(根)初始化,然后通过递归调用向下传递到每个节点。这很好,但据我所知,它在下树的路上从未改变过。它只是原封不动地传了过去。因此,对于 node_data.num_found
的第一次检查将始终为假。
更糟糕的是,由于 node_data
在树下的路径上总是相同的 ((0, False)
),下面这行尝试添加当前节点的运行总和的值(value):
new_running_sum = node.val + node_data.running_sum
将始终将 node.val
添加到 0,因为 node_data.running_sum
始终为 0。
希望这很清楚,我意识到这有点难以解释。
但尝试非常清楚地思考沿着树向下流动的信息(在递归调用的参数中)与沿着树向上流动的信息(在递归调用的返回值中)将使这更清楚一点。
关于python - 根到叶算法错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50532690/