【BFS】 117. 填充每个节点的下一个右侧节点指针 II

117. 填充每个节点的下一个右侧节点指针 II

解题思路

首先，检查根节点是否为空。如果为空，直接返回null。

创建一个队列（Queue）用于层序遍历，将根节点加入队列。

进入循环，循环条件为队列非空。在每一轮循环中，首先获取当前队列的大小（sz），以便知道当前层有多少节点需要处理。

在处理当前层的节点时，使用一个辅助指针pre来记录上一个处理过的节点。初始时，将pre置为null。

通过内部循环，依次处理当前层的每个节点。在处理节点时，如果当前节点的索引（i）大于0，说明这不是该层的第一个节点，将上一个节点（pre）的next指针指向当前节点（cur）。

更新pre为当前节点，然后检查当前节点的左右子节点是否存在，如果存在，则将它们加入队列，以便在下一轮循环中继续处理。

循环结束后，当前层的所有节点的next指针已经正确连接。

重复这个过程，直到队列为空，即所有层的节点都被遍历和连接。

最后返回根节点，整个二叉树的层序遍历和next指针连接完成

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        // 二叉树的层序遍历
        if(root == null){
            return null;
        }

        Queue<Node> queue = new LinkedList<>();// 创建队列
        queue.offer(root);

        while(!queue.isEmpty()){
            // 计算队列尺寸
            int sz = queue.size();

            // 遍历当前层的所有节点
            Node pre = null;

            for(int i = 0; i < sz; i++){
                Node cur = queue.poll();
                if(i > 0){
                    pre.next = cur;
                }

                pre = cur;
                if(cur.left != null){
                    queue.offer(cur.left);
                }

                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }

           
        }

        return root;
    }
}