力扣第116题：填充每个节点的下一个右侧节点指针 - C语言解法
题目描述
给定一个完美二叉树，其每个节点都包含一个额外的next指针，该指针指向该节点的右侧邻居。如果不存在右侧邻居，则该指针应该为NULL。填充所有节点的next指针，并返回修改后的树。
解题思路
1. 题目分析
完美二叉树的定义是：所有叶子节点都在同一层，且每个父节点都有两个子节点。
我们需要填充每个节点的next指针，使得每个节点指向其右侧的邻居节点。如果该节点是当前层的最后一个节点，则其next指针应该指向NULL。
2. 思路
- 由于题目中的树是完美二叉树，我们可以利用层次遍历的方式来逐层链接节点。
- 我们可以通过
next指针来建立跨层链接。假设节点A已经完成了next指针的设置，可以利用A的next指针将B的next指针设置好。
3. 解法
- 我们使用一个指针
start来标记每一层的开始节点。每层的节点可以通过当前节点的next指针来连接。 - 从当前层的
start节点开始，遍历该层的所有节点，并利用它们的next指针来连接下一层的节点。
4. 具体步骤
- 使用一个指针
start指向当前层的最左边的节点。 - 从当前层的
start节点开始，逐一遍历该层的节点并设置它们的next指针。 - 对于每个节点，连接它的两个子节点的
next指针。 - 将
start指向下一层的最左边的节点，重复上述过程直到遍历完所有层。
5. 时间复杂度
由于每个节点只会被访问一次，时间复杂度为 O ( n ) O(n) O(n)，其中 n n n是树中节点的个数。
6. 空间复杂度
我们只使用了常数空间来保存指针，因此空间复杂度为 O ( 1 ) O(1) O(1)。
C语言代码实现
#include <stdio.h>
#include <stdlib.h>// Definition for a Node.
struct Node {int val;struct Node *left;struct Node *right;struct Node *next;struct Node() : val(0), left(NULL), right(NULL), next(NULL) {}
};// 层次遍历的解决方案
struct Node* connect(struct Node* root) {if (!root) return NULL;struct Node* start = root; // 当前层最左的节点// 遍历每一层while (start) {struct Node* current = start;// 遍历当前层while (current) {if (current->left) current->left->next = current->right; // 左子树连接右子树if (current->right && current->next) current->right->next = current->next->left; // 右子树连接下一节点的左子树current = current->next; // 移动到下一节点}// 移动到下一层start = start->left;}return root;
}// 辅助函数：创建树节点
struct Node* createNode(int val) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->val = val;newNode->left = NULL;newNode->right = NULL;newNode->next = NULL;return newNode;
}int main() {// 示例：创建一个简单的完美二叉树struct Node* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);root->right->left = createNode(6);root->right->right = createNode(7);// 填充 next 指针connect(root);// 输出根节点的 next 指针（应该是 NULL）printf("Root's next: %p\n", root->next); // NULLreturn 0;
}
代码解析
1. Node结构体
struct Node {int val;struct Node *left;struct Node *right;struct Node *next;
};
每个节点有val（节点的值）、left（指向左子节点的指针）、right（指向右子节点的指针）以及next（指向右侧邻居节点的指针）。
2. connect函数
struct Node* connect(struct Node* root) {if (!root) return NULL;struct Node* start = root; // 当前层最左的节点while (start) {struct Node* current = start;while (current) {if (current->left) current->left->next = current->right; // 左子树连接右子树if (current->right && current->next) current->right->next = current->next->left; // 右子树连接下一节点的左子树current = current->next;}start = start->left;}return root;
}
- 外层
while (start)遍历每一层，从当前层的最左节点start开始。 - 内层
while (current)遍历当前层的每一个节点，设置next指针：- 将左子树的
next指针指向右子树。 - 如果右子树存在并且当前节点有
next，则将右子树的next指针指向当前节点next的左子树。
- 将左子树的
3. createNode函数
该函数用于创建新的树节点，并初始化节点的val、left、right和next指针。
4. 主函数
在main函数中，我们创建了一棵简单的完美二叉树，调用connect函数填充每个节点的next指针，并输出根节点的next指针。
