题目：
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
代码：
/**
* 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) return;
deque<TreeLinkNode *> curr, next;
curr.push_back(root);
while ( !curr.empty() )
{
TreeLinkNode dummy(-);
TreeLinkNode *pre = &dummy;
while ( !curr.empty() )
{
TreeLinkNode *tmp = curr.front(); curr.pop_front();
pre->next = tmp;
if (tmp->left) next.push_back(tmp->left);
if (tmp->right) next.push_back(tmp->right);
pre = tmp;
}
pre->next = NULL;
std::swap(curr, next);
}
}
};
tips：
广搜思路（有些违规，因为不是const extra space）
每一层设立一个虚拟头结点，出队的同时pre->next = tmp
=====================================
学习了另外一种思路，可以不用队列的数据结构，这样就符合const extra space的条件了。代码如下：
/**
* 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) {
TreeLinkNode *pre;
TreeLinkNode *curr;
TreeLinkNode *next_first; // store next level's first not null node
curr = root;
while ( curr ){
// move to next tree level
TreeLinkNode dummy(-);
pre = &dummy;
next_first = NULL;
// connect the curr level
// record the first not null left or right child of the curr level as for the first node of next level
while ( curr ){
if ( !next_first ){
next_first = curr->left ? curr->left : curr->right;
}
if ( curr->left ){
pre->next = curr->left;
pre = pre->next;
}
if ( curr->right ){
pre->next = curr->right;
pre = pre->next;
}
curr = curr->next;
}
curr = next_first;
}
}
};
tips：
这套代码的大体思路是数学归纳法
1. root节点的root->next按照题意是NULL
2. 处理root的left节点和right节点之间的next关系
...如果知道了第n-1层的node之间的next关系，则可以得到第n层node节点之间的next关系...
按照这套思路，就可以写出上述的代码。
这里有两个细节需要注意：
a. next_first不一定是left还是right，这个要注意，只要next_first一直为NULL就要一直找下去。
b. 设立一个dummy虚node节点，令pre指向dummy，可以不用判断pre为NULL的情况，简化判断条件。
另，回想为什么level order traversal的时候必须用到队列，可能就是因为没有每一层之间的next关系。
==========================================
第二次过这道题，直接看常数空间复杂度的思路，重新写了一遍AC。
/**
* 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) {
TreeLinkNode* curr = root;
while ( curr )
{
TreeLinkNode* pre = new TreeLinkNode();
TreeLinkNode* next_level_head = NULL;
while ( curr )
{
if ( !next_level_head )
{
next_level_head = curr->left ? curr->left : curr->right;
}
if ( curr->left )
{
pre->next = curr->left;
pre = pre->next;
}
if ( curr->right )
{
pre->next = curr->right;
pre = pre->next;
}
curr = curr->next;
}
curr = next_level_head;
}
}
};