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

构建每层单链表 + 维护头尾节点
本题不能用Leetcode–Java–116. 填充每个节点的下一个右侧节点指针的思路，因为不是满二叉树，不确定next在哪，即便下一个结点也可能无左右孩子。

1. 维护下一层的单链表。每次遍历下一层前先构造出下一层的单链表。
2. 维护每一层的头结点，每一层单链表加入结点时，实际上是加入到尾结点，所以记录还要尾结点。遍历的时候往下一层就是赋值为虚拟头结点的下一个。
   
   

class Solution {
    public Node connect(Node root) {
         if (root == null) return root;
         Node cur = root;
         while (cur != null) {
             //下一层的虚拟头结点， 尾结点
             Node head = new Node(-1);
             Node tail = head;
             for (Node p = cur; p != null; p = p.next) {
                 if (p.left != null) {
                     //尾插法加入结点
                     tail.next = p.left;
                     tail = p.left;
                 }
                 if (p.right != null) {
                     tail.next = p.right;
                     tail = p.right;
                 }
             }
             //更新为下一层第一个结点
             cur = head.next;
         }
         return root;
    }
}