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
解法：
这里新建一个无用节点，其next域初始时指向层的首节点，后续随着计算会指向下层的首个节点。
tail=newHead
tail表示下层的首节点，初始时下层和上层是相同值，cur表示上层节点遍历指针，
当cur->left 不为空时：tail->next=cur->left;tail=tail->next;
当cur->right 不为空时，tail->next=cur->right;tail=tail->next;
这样，如果下层有数据，则 自然随着tail.next的第一次修改，使newHead.next指向下层的第一个元素，
在遍历完上层节点时，tail->next要置为NULL，这能防止没有下层节点时，newHead的值没有被修改，仍然指向上层的首节点。
该方法能有效减少判断是否有下层节点的if语句。
void connect(TreeLinkNode *root) {
if(!root)
return;
root->next=NULL;
TreeLinkNode *newHead=new TreeLinkNode(0);
newHead->next=root;
TreeLinkNode *cur=NULL;
TreeLinkNode *tail=NULL;
while(newHead->next){
cur=newHead->next;
tail=newHead;
for(;cur;cur=cur->next){
if(cur->left){
tail->next=cur->left;//left/right在第一次进入时，会因为tail->next的修改使newHead指向下层首节点。
tail=tail->next;
}
if(cur->right){
tail->next=cur->right;
tail=tail->next;
}
}
tail->next=NULL;
//tail 指向NULL能防止因没有下层节点而时newHead的值不能正确指向NULL的错误。
}
delete newHead;
}117. Populating Next Right Pointers in Each Node II
原文：http://searchcoding.blog.51cto.com/1335412/1752102