#yyds干货盘点# LeetCode程序员面试金典：填充每个节点的下一个右侧节点指针

题目：

给一棵完美的二叉树，所有的叶节点都在同一层，每个父节点都有两个子节点。二叉树的定义如下:

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

填满它的每一个 next 指针，让指针指向下一个右节点。如果找不到下一个右节点，它将被发现 next 指针设置为 NULL。

在初始状态下，所有next 所有的指针都设置为 NULL。

示例 1：

输入：root = [1，2，3，4，6，7]

输出:[1，#，2，3，#，4，5，6，7]

说明:给定二叉树如图: A 所示，你的函数应该填充它的每个函数 next 指针指向下一个右节点，如图所示 B 所示。序列化输出按层序排列，同一层节点由同一层节点排列 next “##” 标志着每一层的结束。

示例 2:

输入：root = []

输出：[]

代码实现：

class Solution {    public Node connect(Node root) {        if (root == null) {            return root;        }                // 同时，初始化队列将第一层节点添加到队列中，即根节点        Queue<Node> queue = new LinkedList<Node>();         queue.add(root);                // 外层的 while 层数是循环迭代的        while (!queue.isEmpty()) {                        // 记录当前队列的大小            int size = queue.size();                        // 遍历这一层的所有节点            for (int i = 0; i < size; i++) {                                // 从团队中提取元素                Node node = queue.poll();                                // 连接                if (i < size - 1) {                    node.next = queue.peek();                }                                // 扩展下一层节点                if (node.left != null) {                    queue.add(node.left);                }                if (node.right != null) {                    queue.add(node.right);                }            }        }                // 返回根节点        return root;    }}