基于循环的方法：
void connect(TreeLinkNode *root) {
if (root == NULL) return;
TreeLinkNode * start = root;
TreeLinkNode * end = root;
TreeLinkNode * levelEnd = root;
while (start != NULL)
{
if (start->left != NULL)
{
end->next = start->left;
end = end->next;
}
if (start->right != NULL)
{
end->next = start->right;
end = end->next;
}
if (start == levelEnd)
{
start = start->next;
levelEnd->next = NULL;
levelEnd = end;
}
else
{
start = start->next;
}
}
}
基于递归的方法
void connect(TreeLinkNode *curQueue) {
if (!curQueue) return;
TreeLinkNode* nextQueue = new TreeLinkNode(-1);//dummy node
TreeLinkNode* head = nextQueue;
while (curQueue)
{
if (curQueue->left)
{
nextQueue->next = curQueue->left;
nextQueue = nextQueue->next;
}
if (curQueue->right)
{
nextQueue->next = curQueue->right;
nextQueue = nextQueue->next;
}
curQueue = curQueue->next;
}
nextQueue = head;
head = head->next;
delete nextQueue;
connect(head);
}