平衡的二叉树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都会递增。我们正试图在树中找到一个特定的节点。最糟糕的情况是我们必须在找到它之前搜索树中的所有节点。因此，max_stack_depth应该是1,000,000？

如果你看看stack_depth何时递增，那么看起来我们每次访问节点时都会递增。在我们的例子中，我们每次都访问每个节点。因为在找到正确的节点时停止算法时没有返回条件。

有人可以试着向我解释他们的思考过程。

Answer 1

您必须添加它们，而不是将每个图层上的节点数相乘。例如，前四个层中的节点数是1+2+4+8=15，而不是1*2*4*8=64。

                #                      1
      #                   #          + 2
  #       #           #       #      + 4
#   #   #   #       #   #   #   #    + 8 = 15

通常，第一个n层中的节点数是2**(n+1)-1。您可以使用对数来获得正确的功率并获得该数字的最低点。如果你想减少那个数字，你还必须从功率中减去一个。

>>> math.floor(math.log(1000000, 2))
19
>>> sum(2**i for i in range(1, 20))
1048574

关于你的编辑：是的，stack_depth随每个节点递增，但你正在递增一个局部变量。增量将传递给子节点（作为参数传递）但不传递给兄弟节点，即级别为n的所有节点将使用stack_depth == n-1调用（假设它在第一级开始为0）。因此，max_stack_depth应该是19（或20，如果它以1开头）访问树的前19个级别中的~1,000,000个节点。