题解 | #填充每个节点指向最右节点的next指针#

（1）递归解法
思路就是：当传入的节点的左、右都不是空的时候，连接该节点的左右节点；这样递归结束之后就会形成下图中的样子(红色箭头)

第二步就是判断传入的节点的下一个节点是否为空，不为空，就将当前传入节点的右节点与传入节点的下一个节点的左节点连接，最终形成下图(绿色箭头)

代码如下：

/**
 * 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)
        {
            return;
        }
        if(root->right != NULL && root->left != NULL)
        {
            root->left->next=root->right; //连接左右节点
        }
        if (root->next != NULL && root->right != NULL)
        {
            root->right->next = root->next->left;//连接图中的5、6
        }
        connect(root->left);
        connect(root->right);
    }
};

（2）非递归层次遍历
关键点的连接想法是一致的，主要改变就是不用递归的方法。根据题目的表示可以考虑从层次遍历入手。因此建立next的同时，做层次遍历。

代码如下：

/**
 * 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)
        {
            return;
        }
        while(root->left != NULL)
        {
            TreeLinkNode* node = root;
            while(node != NULL)
            {
                node->left->next = node->right;//连接当前传入节点的左右节点
                if(node->next != NULL)
                {
                    node->right->next=node->next->left;//连接 
                                                       //当前传入节点的右节点 
                                                       //与 
                                                       //传入节点的下一个节点的左节点
                }
                node = node->next;//由于上一步已经建立的连接，
                                  //所以相当于利用next移动节点，直到为空，说明遍历完一层
            }
            root=root->left;//这里就是把传入节点变成下一层的最左侧
        }
    }
};