平衡二叉树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

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

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

通常，第一n层中的节点数为2**(n+1)-1。你可以用对数来得到正确的幂，得到这个数的底数。如果你想要更少的那个数字，你还需要从幂中减去一。在

^{pr2}$

关于您的编辑：是的，stack_depth会随着每个节点而递增，但是您正在递增一个局部变量。增量将携带到子节点（作为参数传递），但不传递给同级节点，即，n级别的所有节点都将用stack_depth == n-1调用（假设它在第一级以0开头）。因此，max_stack_depth应该是19（或者{}，如果它以1开头）来访问树的前19个级别中的~1000000个节点。在