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

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²)。至于每个节点，你都要遍历队列，if attr1==1 for each node.

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

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

Efficient way to search for a node with a specific attribute in a tree and assign the attributes of the tree

algorithm

tree

tree-traversal