填充每个节点的右侧节点指针

一、假设一颗二叉树是满树，将二叉树的节点的next指针指向其右侧节点，没有置空。比如初始二叉树如图：

效果如下：

1.层次遍历
可以观察到进行指针的填充一层一层的进行，层次遍历最为合适
首先根节点入队
①队列不为空，计算一下队列中的元素个数，保证一层一层的进行，创建一个保存前驱的节点
②出队该行节点，前驱节点一直保存着当前出队元素的前一个出队节点，进行连接使用。（该层第一个元素的时候前驱结点为null）如果前驱节点不为null，也就是不是层的第一个节点，进行连接，上一个节点指向该节点。
④前驱节点指向当前节点，左右子节点不为空时分别入队
⑤返回①直至程序结束

    public Node connect(Node root) {
        if (root == null)
            return root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // 每层的节点数量
            int levelCount = queue.size();
            // 前驱节点
            Node preNode = null;
            for (int i = 0; i < levelCount; i++) {
                //出队
                Node node = queue.poll();
                //
                //如果preNode 为空就表示该层的第一个节点，否则的话前驱节点指向该节点进行连接
                if (preNode != null) {
                    preNode .next = node;
                }
                // 当前节点成为前一个节点
                preNode  = node;
                // 左右子节点不为空的时候分别入队
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
        }
        return root;
    }

2.一层一层的进行不需要入队出队，把每层看做是一个链表，每次进行一层遍历的时候将下一层连成一个链表。首先我们用一个节点指向根节点，只要该节点不为null进行循环，如下步骤
①创建一个临时节点（temp进行下一层访问）和前驱节点（pre进行连接）
②遍历当前层，下一层存在的情况下进行连接，因为是满二叉树，所以左子树存在右子树一定存在。pre.next = current .left;pre = pre.next; pre.next = current .right;pre = pre.next;前往该层节点的下一个节点（current = cur.next）
③当前层遍历完之后，进行下一层的遍历（temp.next每次都指向下一层的第一个节点），重复①，②，直到树为空

    public Node connect(Node root) {
        if (root == null)
            return root;
        Node current = root;
        while (current != null) {
            Node temp= new Node(0);
            Node pre = temp;
            while (current != null && current .left != null) {
                pre.next = current .left;
                pre = pre.next;
                pre.next = current .right;
                pre = pre.next;
                current = current .next;
            }
            current = temp.next;
        }
        return root;
    }

当二叉树不是满二叉树的时候也可以用这两种方法解决

层次遍历：

public Node connect(Node root) {
        if(root==null){
            return root;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node pre = null;
            int size = queue.size();
            for(int i=0;i<size;i++){
                Node node = queue.poll();
                if(pre!=null){
                    pre.next = node;
                }
                pre = node;
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
        }
        return root;
    }

链表连接：

 public Node connect(Node root) {
        if(root==null){
            return root;
        }
       Node current = root;
       while(current!=null){
           Node temp = new Node(0);
           Node pre = temp;
           while(current!=null){
               if(current.left!=null){
                   pre.next = current.left;
                   pre = pre.next;
               }
               if(current.right!=null){
                   pre.next = current.right;
                   pre = pre.next;
               }
               current = current.next;
           }
           current = temp.next;
       }
       return root;
    }