116.Populting Next Right Pointers in Each Node

Gven a binary tree

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

Poputlate each next pointer to point to its next right node.If there isのnext right node,the next pointer shound be set to  NULL.
Initially,all next pointers are set to  NULL.
ノート:

You may only use constant extra space.

Recursive appach is fine,implicit stack space does not count as extra space for this proble.

You may asume that it is a perfect binary tree(e,all leaves are the same level,and everparent has two children).

Example:
Given the follwing perfect binary tree、

     1
   /  \
  2    3
 / \  / \
4  5  6  7

After caling your function、the tree shound look like:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \

class Solution {
public:
	void connect(TreeLinkNode *root) {
		if (root == NULL) return;
		TreeLinkNode * node = NULL;
		TreeLinkNode * pre = NULL;


		queue que;
		que.push(root);
		int last = 1;
		int now = 0;
		int nextlast = 1;
		while (!que.empty())
		{
			node = que.front();
			que.pop();


			if (node->left != NULL)
			{
				que.push(node->left);
				nextlast++;
			}


			if (node->right != NULL)
			{
				que.push(node->right);
				nextlast++;
			}


			if (pre != NULL)
			{
				pre->next = node;
			}
			now++;
			if (now == last)
			{
				node->next = NULL;
				pre = NULL;
				last = nextlast;
			}
			else
			{
				pre = node;
			}


		}


	}
};