Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /        2    3
     / \        4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /        2 -> 3 -> NULL
     / \        4-> 5 -> 7 -> NULL

点击打开原题链接

基本上是层次遍历稍微修改下就可以了，算法比较简单，注意下边界条件即可，也可以用把每一层放入vector<vector<> >中去，但是会开辟新的内存，这里

直接判断是否在一层上，代码稍微复杂一点点。

struct TreeLinkNode 
 {
	  int val;
	  TreeLinkNode *left, *right, *next;
	  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
	};
 struct node
 {
	 int level;
	 TreeLinkNode* TLN;
 };
	
	class Solution 
	{
	public:
		void connect(TreeLinkNode *root) 
		{
			if (root == NULL)
			{
				return;
			}
			deque<node> deque_TreeLinkNode;
			node pre,current;
			pre.level = 0;
			pre.TLN = root;
			deque_TreeLinkNode.push_back(pre);
			pre.TLN = NULL;
			while(!deque_TreeLinkNode.empty())
			{
				node temp = deque_TreeLinkNode.front();
				
				if (temp.TLN->left != NULL)
				{
					node left;
					left.level = temp.level+1;
					left.TLN = temp.TLN->left;
					deque_TreeLinkNode.push_back(left);
				}
				if (temp.TLN->right != NULL)
				{
					node right;
					right.level = temp.level+1;
					right.TLN = temp.TLN->right;
					deque_TreeLinkNode.push_back(right);
				}

				current= deque_TreeLinkNode.front();
				deque_TreeLinkNode.pop_front();
				if (pre.TLN == NULL)
				{
					pre.TLN = current.TLN;
					pre.level = current.level;
				//	deque_TreeLinkNode.pop_front();
					continue;
				}
				else
				{
					if (current.level == pre.level)
					{
						
						pre.TLN->next = current.TLN;
						pre=current;
						continue;
					//	current->TLN = NULL;
					//	current->level = 0;
					}
					else
					{
						pre.TLN->next = NULL;
						pre = current;
					}

				}

			}
			pre.TLN->next = NULL;
			

		}
	private:
		
	};

Populating Next Right Pointers in Each Node II