Python二叉树搜索

Question

# stack_depth is initialised to 0
def find_in_tree(node, find_condition, stack_depth):
    assert (stack_depth < max_stack_depth), 'Deeper than max depth'
    stack_depth += 1
    result = []
    if find_condition(node):
        result += [node]
    for child_node in node.children:
        result.extend(find_in_tree(child_node, find_condition, stack_depth))
    return result

我需要帮助理解这段代码。我想回答的问题是

上面的Python函数搜索平衡二叉树的内容。 如果假设上限为1000000个节点，max_stack_depth常量应该设置为多少？

据我所知，这是一个诡计的问题。如果您仔细想想，每次在递归中调用find_in_tree（）函数时，堆栈深度都会增加。我们试图在树中找到一个特定的节点。在我们的例子中，我们每次都在访问每个节点，即使我们找到了正确的节点。因为当找到正确的节点时停止算法时没有返回条件。因此，最大堆栈深度应为1000000？在

有人能解释一下他们的思维过程吗。在

Answer 1

If you look at when stack_depth increments then it looks like we will increment every time we access a node. And in our case we are accessing every single node every time. Because there is no return condition when stops the algorithm when the correct node is found.

这是不正确的。虽然astack_depth变量对于每个被检查的节点都是递增的，但它并不是相同的相同的stack_depth变量。stack_depth是函数中的局部变量。当find_in_tree递归并且递归调用递增stack_depth时，这个不会改变调用者中stack_depth的值。在

stack_depth正在测量此函数运行到完成时发生的递归级别。它的最大值将是您正在检查的树的最大深度。在

也就是说，如果您只知道您有一百万个节点，那么您仍然需要将max_stack_depth步进到一百万，以保证断言不会失败，因为您不知道树有什么形状。可能每个节点都有一个子节点。在这种情况下，您需要递归大约一百万次（可能是999999次，这取决于您的计数方式）来访问每个节点。在

当然，Python会在你到达之前阻止你很久。在

幸运的是，你也知道树是平衡的。这意味着许多节点有两个子节点。这告诉您将找到的最大深度应该接近节点数的logbase2。在

Answer 2

要注意的关键是stack_depth被传递到函数的每个递归调用。如果它是一个平衡的二叉树，那么对find_in_tree的每次调用都会将相同的stack_depth值传递给最多两个子级。请记住，对stack_depth的引用不会在后续对find_in_tree的调用之间共享。它们将自己的版本stack_depth初始化为父调用的值。在

这应该是足够的信息，以便在assert激发之前确定值应该是什么。在