BFS算法变体疑问：两类兄弟节点连接相似代码差异求解

逻辑差异说明 #

两段代码都基于BFS层序遍历实现，核心差异仅在于是否对层与层的连接做隔离：

1. 第一类代码：连接同层相邻兄弟节点 #

class Solution {
public:
    Node* connect(Node* root) {
        return helper(root);
    }
    
    Node* helper(Node* root)
    {
        if(root==NULL)           
            return root;
        
        queue<Node*>queue;
        queue.push(root);
        
        while(!(queue.empty()))
        {
            int levelsize=queue.size();
            Node* prev=NULL;
            
            for(int i = 0  ; i < levelsize ; i++)
            {
                Node* current=queue.front();
                queue.pop();
                
                if(prev!=NULL)
                    prev->next=current;
                
                prev=current;
                
                if(current->left!=NULL)
                    queue.push(current->left);
                if(current->right!=NULL)
                    queue.push(current->right);
                
            }   
        }

        return root;
    }
};

这段代码的核心是在while循环内部加了一层遍历当前层所有节点的for循环，每处理新的一层之前都会把prev重置为NULL：

• 仅同层的相邻节点会建立next关联
• 每一层的最后一个节点的next保持为NULL，不会和下一层的第一个节点连通
  最终效果是树的每一层各自形成独立的单链表。

2. 第二类代码：按层序顺序全局连接所有节点 #

你贴出的第二段代码存在笔误，prev变量定义在while循环内部会导致每次循环都被重置为NULL，所有next指针都无法赋值。正确的实现逻辑是把prev放到while循环外初始化，不需要分层遍历的逻辑：

class Solution {
public:
    Node* connect(Node* root) 
    {
       return helper(root);
    }
    
    Node* helper(Node* root)
    {
        if(root==NULL)           
            return root;
        
        queue<Node*>queue;
        queue.push(root);
        Node* prev=NULL; // prev移到while循环外部初始化
        
        while(!(queue.empty()))
        {
            Node* current=queue.front();
            queue.pop();
            
            if(prev!=NULL)
                prev->next=current;
            
            prev=current;
            
            if(current->left!=NULL)
                queue.push(current->left);
            if(current->right!=NULL)
                queue.push(current->right);
        }
        return root;
    }
};

这段逻辑不再做层边界隔离：

• 所有节点按照BFS层序遍历的先后顺序建立next关联
• 前一层的最后一个节点的next会指向下一层的第一个节点
  最终效果是整棵树所有节点形成一个完整的单链表。

适用场景 #

• 同层连接实现：对应LeetCode 116、117考点，常用于需要分层处理节点的场景，比如输出树的右视图、计算每层节点的平均值/总和、分层打印树结构等。
• 全局层序连接实现：适用于需要把树拍平为层序顺序线性结构的场景，比如层序序列化树、批量按遍历顺序处理所有节点、不需要区分层边界的快速遍历等。

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