填充每个节点指向最右节点的next指针

//不能用递归
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root)
            return;
        TreeLinkNode *p = root, *q;
        while (p->left) {
            q = p;
            while (q) {
                q->left->next = q->right;
                if (q->next)
                    q->right->next = q->next->left;
                q = q->next;
            }
            p = p->left;
        }
    }
}; 

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL)
			return;
        if (root->left!=NULL && root->right!=NULL)
            root->left->next = root->right;
        if (root->next != NULL &&root->right!=NULL){
            root->right->next = root->next->left;
        }
        connect(root->left);
        connect(root->right);
    }
};

import java.util.LinkedList;
import java.util.Scanner;

public class Solution {
    public void connect(TreeLinkNode root) {
        
        if (root== null) return;

        LinkedList<TreeLinkNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int length = queue.size();	//length存储的是目前这一层的长度
            for (int i = 0; i < length; i++) {
                TreeLinkNode curNode = queue.poll();
                if (i == length - 1) {	//length表示是这一层最后一个节点，它的next为null
                    curNode.next = null;
                }else {
                    curNode.next = queue.peek();
                }
            if(curNode.left != null) queue.offer(curNode.left);
            if(curNode.right != null) queue.offer(curNode.right);
            }
        }
    }
}

 //队列层次遍历
//一二问题都适用
void connect(TreeLinkNode *root) {
        if(root==NULL)
            return;
        TreeLinkNode *tail=root;
        TreeLinkNode *temp;
        queue<TreeLinkNode*> q;
        q.push(root);
        while(!q.empty()){
            temp=q.front();
            q.pop();
            if(temp->left!=NULL)
                q.push(temp->left);
            if(temp->right!=NULL)
                q.push(temp->right);
            if(temp==tail){
                temp->next=NULL;
                tail=q.back();
            }
            else{
                temp->next=q.front();
            }
        }
    }

/**

 * Definition for binary tree with next pointer.

 * struct TreeLinkNode {

 *  int val;

 *  TreeLinkNode *left, *right, *next;

 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}

 * };

 */

class Solution {

public:

    void connect(TreeLinkNode *root)

    {

        if(root!=NULL)

        {   // 如果结点的左右孩子都存在，则让左孩子的 next 指向右孩子

            if(root->left != NULL && root->right != NULL)

            {

                root->left->next = root->right;

            }

             // 如果结点的右侧有兄弟结点，并且兄弟结点的左孩子存在

             // 则让该结点右孩子的 next 指向其兄弟结点的左孩子

            if(root->next != NULL && root->next->left != NULL)

            {

                root->right->next = root->next->left;

            }

            // 递归处理左子树

            connect(root->left);

            // 递归处理右子树

            connect(root->right);

        }

    }

辅助队列 
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        Queue<TreeLinkNode> q=new LinkedList<TreeLinkNode>();
        q.add(root);
        q.add(null);
        while(!q.isEmpty()){
            TreeLinkNode node=q.remove();
            if(!q.isEmpty()){
               node.next=q.peek();
               if(node.left!=null)
                   q.add(node.left);
               if(node.right!=null)
                   q.add(node.right);
               if(q.peek()==null){
                   q.add(null);
                   q.remove();
               }
           }               
        }
    }
}

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        
        //由于初值都是null，因此只需要把有next的找出来，变动即可
        while(root.left != null){
            TreeLinkNode node = root;
            while(node != null){
                if(node.left != null) node.left.next = node.right;//完全二叉树，左子树有右子树就有
                if(node.next != null) node.right.next = node.next.left;
                //从左到右遍历同层的所有节点
                node = node.next;
            }
            //每次都从该层的最左边开始遍历
            root = root.left;
        }
    }
}

package day01;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public Node connect(Node root) {

        if (root == null) {
            return root;
        }

        // Initialize a queue data structure which contains
        // just the root of the tree
        Queue<Node> Q = new LinkedList<Node>();
        Q.add(root);

        // Outer while loop which iterates over
        // each level
        while (Q.size() > 0) {//迭代树🌲的每一层 要队里还有元素就循环

            // Note the size of the queue
            int size = Q.size();//队列中元素的个数

            // Iterate over all the nodes on the current level

            for(int i = 0; i < size; i++) {//迭代每一层的每一个元素
                // Pop a node from the front of the queue
                Node node = Q.poll();//队中的第一个元素出队
                // This check is important. We don't want to
                // establish any wrong connections. The queue will
                // contain nodes from 2 levels at most at any
                // point in time. This check ensures we only
                // don't establish next pointers beyond the end
                // of a level
                if (i < size - 1) {
                    node.next = Q.peek();//只要不是已经遍历到这一层最后一个元素 就把next指向队首元素,否则不执行
                }

                // Add the children, if any, to the back of
                // the queue
                if (node.left != null) {
                    Q.add(node.left);
                }
                if (node.right != null) {
                    Q.add(node.right);
                }
            }
        }

        // Since the tree has now been modified, return the root node
        return root;
    }
}

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(!root)return;
        queue<TreeLinkNode*>que;
        que.push(root);
        TreeLinkNode* mostRight=root;
        while(!que.empty()){
            TreeLinkNode* cur=que.front();
            que.pop();
            if(mostRight==cur)mostRight=cur->right;
            else cur->next=que.front();
            if(cur->left)que.push(cur->left);
            if(cur->right)que.push(cur->right);
        }
    }
};

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL)
            return;
        else
            connectNext(root);
    }
    
    void connectNext(TreeLinkNode *root)
    {
        if(root->left == NULL || root->right == NULL)
            return ;
        else
        {
            TreeLinkNode *l = root->left,*r = root->right;
            
            //对每层左子树最右结点和右子树最左结点进行连接

            l->next = r;
            while(l->right != NULL && r->left != NULL)
            {
                l = l->right;
                r = r->left;
                l->next = r;
            }
            
            //对左子树和右子树进行递归
            connectNext(root->left);
            connectNext(root->right);
        }
    }
};

/* 
首先，不能使用层次遍历的思路，因为不满足常量空间的限制（递归不纳入常量空间限制，在leetcode上的原题中有说明）
使用递归求解的思路：
对于一个设置好next值的节点node，若其左右节点均存在，则
其左儿子的next设为node的右儿子
右儿子的next分情况讨论：
    若node->next不存在，则右儿子的next设为NULL
    若node->next存在，则右儿子的next设为node->next->left
按照上述步骤遍历二叉树即可
*/
class Solution {
public:
    void connect(TreeLinkNode *root) 
    {
        if(root == NULL || root -> left == NULL) return;
        
        // left son
        root -> left -> next = root -> right;
        // right son
        if(root -> next)
            root -> right -> next = root -> next -> left;
        connect(root -> left);
        connect(root -> right);
        return;
    }
};

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        /*法一
          利用队列 层次遍历 即可  空间复杂度O(n)
          先将右节点入队列，将上一次遍历的节点设为本次遍历节点的next即可
            
        if(!root) return;
        queue<TreeLinkNode *> Q;
        Q.push(root);
        TreeLinkNode *pre=NULL;
        while(!Q.empty()){
            int row_num = Q.size();
            for(int i=0;i<row_num;i++){
                TreeLinkNode *tmp = Q.front();
                Q.pop();
                tmp->next = pre;
                pre = tmp;
                if(tmp->right)
                    Q.push(tmp->right);
                if(tmp->left)
                    Q.push(tmp->left);
            }
            pre = NULL;
        }
        return;
        */

        /*法二
       不用层次遍历, 每次指针指向该层最左边，然后进行层次遍历，直到为NULL
       下一次循环则指向下一层的最左边，依次下去..
        */
        if(!root) return;
        TreeLinkNode *p = root, *q;
        while(p->left!=NULL){
            q = p;
            while(q!=NULL){
                q->left->next = q->right;
                if(q->next!=NULL){
                    q->right->next = q->next->left;
                }
                q = q->next;
            }
            p = p->left;
        }
        return;
    }
};

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode begin = root;
        while(root!=null&&root.left!=null) {
            if(root.next!=null) {
                root.left.next = root.right;
                root.right.next = root.next.left;
                root = root.next;
            }
            else {
                root.left.next=root.right;
                root = begin.left;
                begin = root;
            }
        }
    }
}

// 层序遍历，每次从右往左遍历将上一次遍历节点设置为本次的next节点即可
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeLinkNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeLinkNode pre = null;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeLinkNode node = queue.poll();
                node.next = pre;
                pre = node;
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                size--;
            }
            pre = null;
        }
    }
}

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) 
            return;
        if(root.left != null){
            root.left.next = root.right;
        }
        if(root.next != null && root.left != null){
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }
}

package populating_next_right_pointers_in_each_node;


import java.util.ArrayList;

/**
 * Populate each next pointer to point to its next right node.
 * If there is no next right node, the next pointer should be set toNULL.
 * Initially, all next pointers are set toNULL.
 * Note:
 * You may only use constant extra space.
 * You may assume that it is a perfect binary tree (ie, all leaves are at the
 * same level, and every parent has two children).
 *
 * For example,
 * Given the following perfect binary tree,
 *          1
 *        /  \
 *       2    3
 *      / \  / \
 *     4  5  6  7
 *
 * After calling your function, the tree should look like:
 *          1 -> NULL
 *        /  \
 *       2 -> 3 -> NULL
 *      / \  / \
 *     4->5->6->7 -> NULL
 */
public class Solution {

    public class TreeLinkNode {
        int val;
        TreeLinkNode left, right, next;
        TreeLinkNode(int x) { val = x; }
    }

    /**
     * 树的层次遍历，由于使用了空间复杂度 O(n)
     */
    public void connect1(TreeLinkNode root) {
        if (root == null)
            return;

        ArrayList<TreeLinkNode> curLevel = new ArrayList<>();
        curLevel.add(root);

        while (!curLevel.isEmpty()) {
            ArrayList<TreeLinkNode> nextLevel = new ArrayList<>();
            // 遍历当前层
            TreeLinkNode node = curLevel.get(0);
            TreeLinkNode nextNode;

            // 保存下一层节点
            if (node.left != null) nextLevel.add(node.left);
            if (node.right != null) nextLevel.add(node.right);

            for (int i = 1; i < curLevel.size(); i++) {
                // 修改 next 指针
                nextNode = curLevel.get(i);
                node.next = nextNode;
                node = nextNode;

                // 保存下一层节点
                if (node.left != null)
                    nextLevel.add(node.left);
                if (node.right != null)
                    nextLevel.add(node.right);
            }
            curLevel = nextLevel;
        }
    }

    /**
     * 递归的方式实现，空间复杂度为调用栈的深度
     * 边界条件几种方式
     * 1、root 为 null 直接返回
     * 2、root 根节点下的左右子树的 next 链接
     * 3、跨 root 根节点的子树的 next 链接
     */
    public void connect2(TreeLinkNode root) {
        if (root == null)
            return;

        // root 根节点下的左右子树的 next 链接
        if (root.left != null && root.right != null)
            root.left.next = root.right;
        // 跨 root 根节点的子树的 next 链接
        if (root.right != null && root.next != null)
            root.right.next = root.next.left;

        // 递归connect以root左右子树节点为根节点的子树
        connect2(root.left);
        connect2(root.right);
    }

    /**
     * 非递归的方式实现
     *
     * 从最左边的节点开始更新 next 指针，同样两种情况：
     * root.left.next -> root.right
     * root.right.next -> root.next.left
     */
    public void connect(TreeLinkNode root) {
        if (root ==null)
            return;

        TreeLinkNode p = root;
        TreeLinkNode updateRoot;

        // 从根节点 p 开始，从最左边的节点开始修改p的下一层的左右子树节点的 next 指针
        while (p.left != null) {
            updateRoot = p;
            while (updateRoot != null) {
                // 第一种情况
                updateRoot.left.next = updateRoot.right;
                // 第二种情况
                if (updateRoot.next != null) {
                    updateRoot.right.next = updateRoot.next.left;
                }
                // 更新的节点向右移动
                updateRoot = updateRoot.next;
            }
            p = p.left;
        }
    }
}

/*
	 * 推荐解答
	 */
	public void connect(TreeLinkNode root) {
		TreeLinkNode level_start = root;
		while (level_start != null) {
			TreeLinkNode cur = level_start;
			while (cur != null) {
				if (cur.left != null)
					cur.left.next = cur.right;
				if (cur.right != null && cur.next != null)
					cur.right.next = cur.next.left;

				cur = cur.next;
			}
			level_start = level_start.left;
		}
	}

	/*
	 * My Solution
	 */
	public void connect_2(TreeLinkNode root) {
		TreeLinkNode levelFirst = root;
		TreeLinkNode cur = levelFirst;
		while (cur != null) {
			if (cur.left != null)
				cur.left.next = cur.right;
			if (cur.right != null && cur.next != null) {
				cur.right.next = cur.next.left;
			}
			if (cur.next != null)
				cur = cur.next;
			else {
				levelFirst = levelFirst.left;
				cur = levelFirst;
			}

		}
	}