LeetCode 116. Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL .
Initially, all next pointers are set to NULL .
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

This one is actually Level-Order Traversal.

#include <iostream>
#include <queue>
using namespace std;

struct TreeLinkNode {
  int val;
  TreeLinkNode *left;
  TreeLinkNode* right;
  TreeLinkNode* next;
  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
/*
             1
          2    3

        changed into

            1->NULL
          2 --> 3 ->NULL
*/
TreeLinkNode* setUpLinkTree() {
  TreeLinkNode* root = new TreeLinkNode(1);
  root->left = new TreeLinkNode(2);
  root->right = new TreeLinkNode(3);
  return root;
}
void connect(TreeLinkNode* root) {
  if(!root) return;
  queue<TreeLinkNode*> nodes;
  queue<TreeLinkNode*> nextLevel;
  nodes.push(root);
  while(!nodes.empty()) {
    TreeLinkNode* tmp = nodes.front();
    nodes.pop();
    if(tmp->left) nextLevel.push(tmp->left);
    if(tmp->right) nextLevel.push(tmp->right);
    while(!nodes.empty()) {
      TreeLinkNode* tmp_next = nodes.front();
      nodes.pop();
      tmp->next = tmp_next;
      tmp = tmp_next;

      if(tmp_next->left) nextLevel.push(tmp_next->left);
      if(tmp_next->right) nextLevel.push(tmp_next->right);
    }
    swap(nodes, nextLevel);
  }
}

void printLinkTree(TreeLinkNode* root) {
  if(!root) return;
  cout << "root value is: " << root->val << " next value is: " << ((root->next == NULL) ? 0 : (root->next)->val) << endl;
  printLinkTree(root->left);
  printLinkTree(root->right);
}

int main(void) {
  TreeLinkNode* root = setUpLinkTree();
  connect(root);
  printLinkTree(root);
}