二叉树节点病毒感染扩散异常排查：为何无法感染全部节点？

核心问题定位 #

病毒扩散的相邻节点应包含父节点、左子节点、右子节点，但当前实现大概率仅遍历了感染节点的左右子节点，完全忽略了父节点这条反向扩散路径。当以C为起点时，代码仅感染了C的子节点F，却未将C的父节点A纳入扩散队列，导致后续无法向A及其他分支扩散，最终停留在C、F两个节点。

修复方案 #

1. 给二叉树节点添加父节点引用 #

在节点结构中增加parent指针，构建树时同步维护父节点关系，让每个节点能访问到它的父节点，这是反向扩散的基础。

2. BFS遍历覆盖所有相邻节点 #

每轮感染时，对当前节点需同时检查父节点、左子节点、右子节点，确保符合条件（非空、未感染）的节点被加入扩散队列。

3. 标记已感染节点避免重复处理 #

通过节点内的布尔字段或哈希集合记录已感染状态，防止同一节点被多次加入队列。

修复后的核心代码示例（C语言） #

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 带父节点的二叉树节点定义
typedef struct TreeNode {
    char val;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
    bool is_infected;
} TreeNode;

// 创建新节点
TreeNode* createNode(char val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = node->parent = NULL;
    node->is_infected = false;
    return node;
}

// 构建树并维护父节点关系
void buildTree(TreeNode* root) {
    root->left = createNode('B');
    root->left->parent = root;
    
    root->right = createNode('C');
    root->right->parent = root;
    
    root->right->right = createNode('F');
    root->right->right->parent = root->right;
}

// 迭代返回每轮感染状态
void infectionIteration(TreeNode* start) {
    if (!start) return;

    TreeNode* queue[100];
    int front = 0, rear = 0;
    start->is_infected = true;
    queue[rear++] = start;

    int round = 0;
    while (front < rear) {
        int currentBatchSize = rear - front;
        printf("第%d轮感染节点：", ++round);
        
        // 记录本轮新感染节点
        char infectedNodes[100];
        int idx = 0;
        for (int i = 0; i < currentBatchSize; i++) {
            TreeNode* curr = queue[front++];
            infectedNodes[idx++] = curr->val;

            // 检查父节点
            if (curr->parent && !curr->parent->is_infected) {
                curr->parent->is_infected = true;
                queue[rear++] = curr->parent;
            }
            // 检查左子节点
            if (curr->left && !curr->left->is_infected) {
                curr->left->is_infected = true;
                queue[rear++] = curr->left;
            }
            // 检查右子节点
            if (curr->right && !curr->right->is_infected) {
                curr->right->is_infected = true;
                queue[rear++] = curr->right;
            }
        }

        // 输出本轮结果
        for (int i = 0; i < idx; i++) {
            printf("%c ", infectedNodes[i]);
        }
        printf("\n");
        
        // 无新节点感染则终止
        if (rear - front == 0) break;
    }
}

int main() {
    TreeNode* root = createNode('A');
    buildTree(root);
    // 以节点C为感染起点
    infectionIteration(root->right);
    return 0;
}

输入输出示例 #

输入：以节点C为感染起点
输出：
第1轮感染节点：C
第2轮感染节点：A F
第3轮感染节点：B

关键注意事项 #

• 病毒扩散是无向的，必须将父节点纳入相邻节点范围，否则会出现单向扩散的死胡同。
• 必须通过标记过滤已感染节点，避免队列中重复加入同一节点导致死循环或无效计算。
• 构建树时要确保父节点指针正确赋值，这是反向扩散的前提条件。

内容的提问来源于stack exchange，提问作者KushKage