https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
接上一题目，输入的树不是perfect的。
在这里深搜就不好使了。因为，在你往下深搜的时候，可能上一行的next还没处理到那里，所以会丢失信息。
利用它的next结构，进行bfs，同时记录下一行的head节点。
/**
* 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 == NULL)
return; TreeLinkNode *NextRowHead = NULL;
TreeLinkNode *NextRowPrev = NULL;
while(root)
{
if(root->left)
{
if(NextRowHead == NULL) // the first element of next row
{
NextRowHead = root->left;
}
else
NextRowPrev->next = root->left; //它前面有点 NextRowPrev = root->left;
}
if(root->right)
{
if(NextRowHead == NULL)
{
NextRowHead = root->right;
}
else
NextRowPrev->next = root->right; NextRowPrev = root->right;
}
root = root->next; if(root == NULL) //begin a new row
{
root = NextRowHead;
NextRowHead = NULL;
NextRowPrev = NULL;
}
}
}
};