Populating Next Right Pointers in Each Node II [leetcode] 空间O(1)的基于循环和基于递归的两种方法
来源：程序员人生 发布时间：2014-10-10 08:00:01 阅读次数：3177次
基于循环的方法：
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);
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
