给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 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. 将子节点记录到下一次的遍历链表中
if (curr->left) {
nextLayerHeadCurr->next = curr->left;
nextLayerHeadCurr = nextLayerHeadCurr->next;
}
if (curr->right) {
nextLayerHeadCurr->next = curr->right;
nextLayerHeadCurr = nextLayerHeadCurr->next;
}
// 2. 处理下一个节点
currLayerHeadCurr = currLayerHeadCurr->next;
// 3. 如果当前层为空了，下一层也为空，跳出
if (currLayerHeadCurr->next == NULL && nextLayerHead.next == NULL) {
break;
}
// 4. 当前层没有要处理的节点了
if (currLayerHeadCurr->next == NULL) {
currLayerHead.next = nextLayerHead.next;
nextLayerHead.next = NULL;
nextLayerHeadCurr = &nextLayerHead;
currLayerHeadCurr = &currLayerHead;
printf("\n");
}
}
return root;
}
思路：遍历当前层的时候，把子节点记录为下一次遍历的下一层，当当前层遍历完的时候，交换当前层和下一层，下一层就为空了。当当前层和下一层的链表都为空的时候，就表示遍历完成了，同时链接也完成了。
