Populating Next Right Pointers in Each Node II [leetcode] 空間O(1)的基于循環和基于遞歸的兩種方法
來源：程序員人生 發布時間：2014-10-10 08:00:01 閱讀次數：3306次
基于循環的方法：
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);
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
