具有树数据结构的时间复杂度

Question

我目前正在使用python处理Tree数据结构。目前，我正在尝试计算子树值，其中子树值等于给定节点的子树中节点的最大值。例如。对于给定的树：

       A(5)
       / \
     C(2) D(8)
      |
     B(10)

C的子树值为10，A的子树值为10，D的子树值为8，依此类推。我试图将以下代码的复杂度从O（n ^ 2）减少到O （n）。也就是说，我试图在不使用嵌套循环的情况下向上移动树。我已经尝试过递归，但是我不太擅长递归，因此下面提供了迭代解决方案。任何帮助，将不胜感激。另外，是否可以在没有递归解决方案的情况下执行此操作？

         node = subtree_a
         while node.parent != None:
             children = node.parent.children
             for child in children:
                 if (child.subtree_value > node.parent.subtree_value):
                     node.parent.set_subtree_val(child.subtree_value)
             node = node.parent\

Answer 1

子树的值仅取决于低于树的节点，因此绝对没有理由在代码中具有自底向上的外部循环。

一种非常简单的自上而下的递归方法是：

def calc_subtree_value(node):
    val = node.value
    for child in node.children: # we don't need a base case, this forks for leaf nodes too
        calc_subtree_value(child)
        if child.subtree_value > val:
            val = child.subtree_value
    node.subtree_value = max_val

这需要O（N）的时间，其中N是子树中节点的数量，因为它恰好访问每个树一次。正如我在评论中所指出的，我们不需要显式的基本情况，因为如果没有子级可以检查较大的子树值，则子级循环将执行我们想要的操作（无）。