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函数搜索平衡二叉树的内容。如果假设上限为 1,000,000 个节点，max_stack_depth 常量应设置为多少？

据我了解，这是一个技巧问题。如果您考虑一下，每次在递归中调用 find_in_tree() 函数时 stack_depth 都会递增。我们正试图在树中找到一个特定的节点。在我们的例子中，即使我们找到了正确的节点，我们每次都会访问每个节点。因为没有 return 条件 when 找到正确的节点时停止算法。因此，max_stack_depth 应该是 1,000,000？

谁能解释一下他们的思维过程。

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.

这是不正确的。虽然 a stack_depth 变量针对每个检查的节点递增，但它不是 same stack_depth 变量。 stack_depth 是函数内的局部变量。当 find_in_tree 递归并且递归调用递增 stack_depth 时，此 不会更改 调用方中 stack_depth 的值。

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

就是说，如果您所知道的是您有一百万个节点，您仍然需要 max_stack_depth 到一百万个以保证断言不会因为您不知道什么而失败 shape 树有。可能每个节点都有一个child。在这种情况下，您将需要递归大约一百万次（可能是 999,999 次，具体取决于您如何计算）来访问每个节点。

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

幸运的是，你也知道这棵树是平衡的。这意味着许多节点有两个 children。这告诉你你会发现的最大深度应该接近节点数的对数基数 2。

Answer 2

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

这应该是足够的信息来确定触发断言之前的值。

Python 二叉树搜索

Python Binary tree search

python

recursion

binary-tree