/*

算法思想：

    实际上是树的层序遍历的应用。

    这道题是每个节点的右向指针这道题的延伸。即不是完美二叉树了。但是还是可以一样的方法，所以这种非递归的解法很通用，因为是用的层次遍历加队列它才不管你是不是完美二叉树呢。需要用到queue来辅助，由于是层序遍历，每层的节点都按顺序加入queue中，而每当从queue中取出一个元素时，将其next指针指向queue中下一个节点即可。需要巧妙的通过给queue中添加空指针NULL来达到分层的目的，使每层的最后一个节点的next可以指向NULL。

*/

//算法实现：

/**

 * 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) return;

        queue<TreeLinkNode*> q;

        q.push(root);

        q.push(NULL);

        while (true) {

            TreeLinkNode *cur = q.front();

            q.pop();

            if (cur) {

                cur->next = q.front();

                if (cur->left)

                    q.push(cur->left);

                if (cur->right)

                    q.push(cur->right);

            }

            else {

                if (q.size() == 0 || q.front() == NULL)

                    return;

                q.push(NULL);

            }

        }

    }

};