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
思路：在前面I的基础上进行一些改进。下层节点的next指针指向需要对上一层的所有节点的左右节点进行遍历，如果不为NULL，则指向。例如节点5的next指向，需要遍历3节点的左右子节点，找到7，则指向。
class Solution {
public:
void connect(TreeLinkNode *root) {
/*****************************************
* 队列的长度最好取10000以上，前面WA是因为队列的长度太小了
* ****************************************/
TreeLinkNode* Q[10000];
int front = 0, rear = -1;
int i,j;
Q[++rear] = root;
if (Q[rear] == NULL)
{
return;
}
int index;
while(front <= rear)
{
index = rear;
for(i = front; i <= index; i++)
{
if (Q[i]->left != NULL)
{
Q[++rear] = Q[i]->left;
if (Q[i]->right != NULL)
{
Q[rear]->next = Q[i]->right;
}
else
{
for(j = i+1; j<=index; j++)
{
if (Q[j]->left != NULL)
{
Q[rear]->next = Q[j]->left;
break;
}
if (Q[j]->right != NULL)
{
Q[rear]->next = Q[j]->right;
break;
}
}
}
}
if (Q[i]->right != NULL)
{
Q[++rear] = Q[i]->right;
for(j = i+1; j<=index; j++)
{
if (Q[j]->left != NULL)
{
Q[rear]->next = Q[j]->left;
break;
}
if (Q[j]->right != NULL)
{
Q[rear]->next = Q[j]->right;
break;
}
}
}
}
front = index + 1;
}
}
};