algorithm - 在树中搜索具有特定属性的节点并分配树的属性的有效方法

Question

我有一棵树。例如下面一个: 根

      a
    /   \
   b     c
  / \   / \
 e   d f   g

树中的每个节点都有一个属性 attr1。如果一个节点的 attr1 的值为 1。那么到该节点的路径上所有节点的 attr2(另一个属性)应该为 1。但是我们不不知道是否有任何节点在其 attr1 中具有值 1。
我要解决这个问题的想法是遍历树(预购)。在遍历时，我将有一个 FIFO 容器(queue)，每次我向下移动时，我都会添加到队列中，而当向上移动时，我会删除下面的节点。所以我总是有当前节点的路径。如果此时节点有attr1 == 1，那么我必须再次迭代路径并将路径中所有节点的attr2设置为2。
但是我不知道是否有更高效的方法来实现这一点？

Answer 1

def update(node):
    if node is None:
        return False
    upd_left = update(node.left)
    upd_right = update(node.right)

    node.attr2 = 1 if upd_left or upd_right or node.attr1 == 1 else node.attr2
    return node.attr2 == 1

我认为这会达到您的预期，因为我们不会一次又一次地遍历队列。 在倾斜树的情况下，您的方法的最坏情况复杂度为 O(n²)。对于每个节点，如果attr1==1对于每个节点，则必须遍历队列。

但是，在上面的代码中，复杂度最多为 O(n)。因为您只访问每个节点一次。