如何将受感染的节点传播到其相邻节点并最终传播到整个二叉树？

Question

我想迭代地返回二叉树的状态，直到感染无法传播到新节点。因此，病毒将传播到任何直接相邻的健康节点，我想在病毒感染的每一轮之后返回树的状态。一旦每个可能的节点都被感染，算法就应该停止。

鉴于“B”是原点，我想要实现的目标（示例）：

这是我到目前为止所拥有的：

from binarytree import Node, build

def build_tree(data):
    if not data or data[0] == 0:
        return None
    root = Node(data[0])
    nodes = [root]
    for i in range(1, len(data), 2):
        node = nodes.pop(0)
        if data[i] != 0:
            node.left = Node(data[i])
            nodes.append(node.left)
        if i + 1 < len(data) and data[i + 1] != 0:
            node.right = Node(data[i + 1])
            nodes.append(node.right)
    return root
    
def infected(node):
    return f"*{node.value}*"

def search_node(root, value):
    if root is None or root.value == value:
        return root
    left_result = search_node(root.left, value)
    right_result = search_node(root.right, value)
    return left_result if left_result else right_result

def virus(node):
    infected_nodes = set()
    current_round = set([node])

    while current_round:
        next_round = set()

        for current_node in current_round:
            neighbors = [child for child in (current_node.left, current_node.right) if child and child.value != 0]

            for neighbor in neighbors:
                if neighbor not in infected_nodes:
                    infected_nodes.add(neighbor)
                    neighbor.value = infected(neighbor)
                    next_round.add(neighbor)

        if infected_nodes == set(current_round):
           break

        print(tree)
        current_round = next_round

输入：

sample = ["A", "B", "C", "D", "E", 0, "F"]
origin_value = "C"

tree = build_tree(sample)
origin_node = search_node(tree, origin_value)

origin_node.value = infected(origin_node)
print(tree)
virus(origin_node)

输出：

从输出中可以看出，C 只传播到 F 并停在那里，它应该传播到 A 和整个二叉树。我在这里做错了什么？

Answer 1

假设每个节点都可以访问自己的父节点，顶层算法是广度优先遍历或原始节点，然后在父节点上重复该算法

Infect the origin node and put that node in a single element list called "the list"

while the list is not empty:
    infect all nodes in the list
    print the tree, as this represents the next iteration
    Update the list to contain all the children of the current list
    
After the above algorithm runs, move up the parent node of the origin node and repeat.

我认为这接近你想要的：

def virus(tree, originNode):
    while True:
        startInfectingDownward(tree, originNode)
        if not originNode.parent:
            break
        originNode = originNode.parent

def startInfectingDownward(tree, originNode):
    if (originNode.isInfected):
        return
    nextSetOfInfections = [originNode]
    while nextSetOfInfections:
       for node in nextSetOfInfections:
           node.isInfected = true
       printTree(tree)
       nextSetOfInfections = getNextSetOfInfections(nextSetOfInfections)


def getNextSetOfInfections(list):
    resultList = []
    for item in list:
       if (item.left and not item.left.isInfected):
           resultList.append(item.left)
       if (item.right and not item.right.isInfected):
           resultList.append(item.right)
    return resultList