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

leetcode 116.填充每个节点的下一个右侧结点指针

news 2025/7/10 2:38:19

1.题目要求:

给定一个二叉树：struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。初始状态下，所有 next 指针都被设置为 NULL 。

在这里插入图片描述
2.做题步骤:
(1)先创建好队列结构体，入队函数，出队函数:

//创建队列结构体
typedef struct queue{struct TreeNode* value;struct queue* next1;
}queue_t;
//入队
void push(queue_t** head,struct Node* data){queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));newnode->value = data;newnode->next1 = NULL;if(*head == NULL){*head = newnode;return;}queue_t* tail = *head;while(tail->next1 != NULL){tail = tail->next1;}tail->next1 = newnode;
}
//出队
struct Node* pop(queue_t** head){struct TreeNode* x = (*head)->value;(*head) = (*head)->next1;return x;
}

(2)设置变量，进行层序遍历:

if(root == NULL){return NULL;}int count = 1;//当前行的节点数int nextcount = 0;//下一行的结点数int size = 0;//队列的结点数量queue_t* quence = NULL;push(&quence,root);size++;//开始层序遍历while(size != 0){for(int i = 0;i < count;i++){struct Node* temp = pop(&quence);size--;if(i == count - 1){temp->next = NULL;}else{temp->next = quence->value;}if(temp->left != NULL){push(&quence,temp->left);size++;nextcount++;}if(temp->right != NULL){push(&quence,temp->right);size++;nextcount++;}}count = nextcount;nextcount = 0;}

全部代码:

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *left;*     struct Node *right;*     struct Node *next;* };*/
//创建队列结构体
typedef struct queue{struct TreeNode* value;struct queue* next1;
}queue_t;
//入队
void push(queue_t** head,struct Node* data){queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));newnode->value = data;newnode->next1 = NULL;if(*head == NULL){*head = newnode;return;}queue_t* tail = *head;while(tail->next1 != NULL){tail = tail->next1;}tail->next1 = newnode;
}
//出队
struct Node* pop(queue_t** head){struct TreeNode* x = (*head)->value;(*head) = (*head)->next1;return x;
}
struct Node* connect(struct Node* root) {if(root == NULL){return NULL;}int count = 1;//当前行的节点数int nextcount = 0;//下一行的结点数int size = 0;//队列的结点数量queue_t* quence = NULL;push(&quence,root);size++;//开始层序遍历while(size != 0){for(int i = 0;i < count;i++){struct Node* temp = pop(&quence);size--;if(i == count - 1){temp->next = NULL;}else{temp->next = quence->value;}if(temp->left != NULL){push(&quence,temp->left);size++;nextcount++;}if(temp->right != NULL){push(&quence,temp->right);size++;nextcount++;}}count = nextcount;nextcount = 0;}return root;
}