当前位置：首页 > article >正文

力扣第116题：填充每个节点的下一个右侧节点指针 - C语言解法

article 2025/1/3 4:24:43

力扣第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)$ ，其中 $n$ 是树中节点的个数。

6. 空间复杂度

我们只使用了常数空间来保存指针，因此空间复杂度为 $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);  // NULL
    
    return 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的左子树。