給定一個二叉樹
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針刁憋，讓這個指針指向其下一個右側(cè)節(jié)點(diǎn)滥嘴。如果找不到下一個右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL职祷。
初始狀態(tài)下氏涩，所有 next 指針都被設(shè)置為 NULL。
image.png
代碼如下：
struct Node* connect(struct Node* root) {
if (!root) return NULL;
struct Node currLayerHead = { 0,NULL,NULL, root };;
struct Node* currLayerHeadCurr = &currLayerHead;
struct Node nextLayerHead = {0,NULL,NULL, NULL};
struct Node* nextLayerHeadCurr = &nextLayerHead;
while (currLayerHeadCurr->next) {
struct Node* curr = currLayerHeadCurr->next;
// 1. 將子節(jié)點(diǎn)記錄到下一次的遍歷鏈表中
if (curr->left) {
nextLayerHeadCurr->next = curr->left;
nextLayerHeadCurr = nextLayerHeadCurr->next;
}
if (curr->right) {
nextLayerHeadCurr->next = curr->right;
nextLayerHeadCurr = nextLayerHeadCurr->next;
}
// 2. 處理下一個節(jié)點(diǎn)
currLayerHeadCurr = currLayerHeadCurr->next;
// 3. 如果當(dāng)前層為空了有梆，下一層也為空是尖，跳出
if (currLayerHeadCurr->next == NULL && nextLayerHead.next == NULL) {
break;
}
// 4. 當(dāng)前層沒有要處理的節(jié)點(diǎn)了
if (currLayerHeadCurr->next == NULL) {
currLayerHead.next = nextLayerHead.next;
nextLayerHead.next = NULL;
nextLayerHeadCurr = &nextLayerHead;
currLayerHeadCurr = &currLayerHead;
printf("\n");
}
}
return root;
}
思路：遍歷當(dāng)前層的時候，把子節(jié)點(diǎn)記錄為下一次遍歷的下一層泥耀，當(dāng)當(dāng)前層遍歷完的時候饺汹，交換當(dāng)前層和下一層，下一層就為空了痰催。當(dāng)當(dāng)前層和下一層的鏈表都為空的時候兜辞，就表示遍歷完成了，同時鏈接也完成了夸溶。
