Medium！
题目描述：
给定一个二叉树
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
说明:
- 你只能使用额外常数空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例:
给定二叉树，
1
/ \
2 3
/ \ \
4 5 7
调用你的函数后，该二叉树变为：
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
解题思路：
这道是之前那道Populating Next Right Pointers in Each Node 每个节点的右向指针的延续，原本的完全二叉树的条件不再满足，但是整体的思路还是很相似，仍然有递归和非递归的解法。我们先来看递归的解法，这里由于子树有可能残缺，故需要平行扫描父节点同层的节点，找到他们的左右子节点。
C++解法一：
// Recursion, more than constant space
class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root) return;
TreeLinkNode *p = root->next;
while (p) {
if (p->left) {
p = p->left;
break;
}
if (p->right) {
p = p->right;
break;
}
p = p->next;
}
if (root->right) root->right->next = p;
if (root->left) root->left->next = root->right ? root->right : p;
connect(root->right);
connect(root->left);
}
};
对于非递归的方法，惊喜的发现之前的方法直接就能用，完全不需要做任何修改，算法思路可参见博客Populating Next Right Pointers in Each Node 每个节点的右向指针http://www.cnblogs.com/grandyang/p/4288151.html
C++解法二：
// Non-recursion, more than constant space
class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root) return;
queue<TreeLinkNode*> q;
q.push(root);
while (!q.empty()) {
int len = q.size();
for (int i = ; i < len; ++i) {
TreeLinkNode *t = q.front(); q.pop();
if (i < len - ) t->next = q.front();
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
}
};
虽然以上的两种方法都能通过OJ，但其实它们都不符合题目的要求，题目说只能使用constant space，可是OJ却没有写专门检测space使用情况的test，那么下面贴上constant space的解法，这个解法也是用的层序遍历，只不过没有使用queue了，我们建立一个dummy结点来指向每层的首结点的前一个结点，然后指针t用来遍历这一层，我们实际上是遍历一层，然后连下一层的next，首先从根结点开始，如果左子结点存在，那么t的next连上左子结点，然后t指向其next指针；如果root的右子结点存在，那么t的next连上右子结点，然后t指向其next指针。此时root的左右子结点都连上了，此时root向右平移一位，指向其next指针，如果此时root不存在了，说明当前层已经遍历完了，我们重置t为dummy结点，root此时为dummy->next，即下一层的首结点，然后dummy的next指针清空。
C++解法三：
// Non-recursion, constant space
class Solution {
public:
void connect(TreeLinkNode *root) {
TreeLinkNode *dummy = new TreeLinkNode(), *t = dummy;
while (root) {
if (root->left) {
t->next = root->left;
t = t->next;
}
if (root->right) {
t->next = root->right;
t = t->next;
}
root = root->next;
if (!root) {
t = dummy;
root = dummy->next;
dummy->next = NULL;
}
}
}
};