162.二叉树：填充每个节点的下一个右侧节点指针（力扣）

代码解决

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
public:Node* connect(Node* root) {queue<Node*> que;  // 定义队列用于层次遍历if (root != NULL) que.push(root);  // 如果根节点不为空，则将根节点加入队列while (!que.empty())  // 当队列不为空时，继续处理{int size = que.size();  // 获取当前层的节点数量Node* node;  // 当前处理的节点Node* prenode;  // 前一个处理的节点for (int i = 0; i < size; i++)  // 遍历当前层的每一个节点{if (i == 0)  // 如果是当前层的第一个节点{prenode = que.front();que.pop();node = prenode;}else  // 如果不是当前层的第一个节点{node = que.front();que.pop();prenode->next = node;  // 将前一个节点的 next 指向当前节点prenode = prenode->next;}if (node->left) que.push(node->left);  // 如果该节点有左子节点，将其加入队列if (node->right) que.push(node->right);  // 如果该节点有右子节点，将其加入队列}prenode->next = NULL;  // 当前层的最后一个节点的 next 设为 NULL}return root;  // 返回根节点}
};

测试代码

#include <iostream>
#include <vector>
#include <queue>using namespace std;// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};class Solution {
public:Node* connect(Node* root) {if (root == NULL) return NULL;  // 如果根节点为空，直接返回 NULLqueue<Node*> que;  // 定义队列用于层次遍历que.push(root);  // 将根节点加入队列while (!que.empty())  // 当队列不为空时，继续处理{int size = que.size();  // 获取当前层的节点数量Node* prenode = NULL;  // 前一个处理的节点，初始化为 NULLfor (int i = 0; i < size; i++)  // 遍历当前层的每一个节点{Node* node = que.front();  // 从队列中取出一个节点que.pop();  // 将该节点从队列中移除if (prenode != NULL) {prenode->next = node;  // 将前一个节点的 next 指向当前节点}prenode = node;  // 更新前一个节点为当前节点if (node->left) que.push(node->left);  // 如果该节点有左子节点，将其加入队列if (node->right) que.push(node->right);  // 如果该节点有右子节点，将其加入队列}prenode->next = NULL;  // 当前层的最后一个节点的 next 设为 NULL}return root;  // 返回根节点}
};// 辅助函数：创建一个测试树
Node* createTestTree() {Node* root = new Node(1);root->left = new Node(2);root->right = new Node(3);root->left->left = new Node(4);root->left->right = new Node(5);root->right->left = new Node(6);root->right->right = new Node(7);return root;
}// 辅助函数：打印树的每一层
void printTreeByLevel(Node* root) {Node* levelStart = root;while (levelStart != NULL) {Node* current = levelStart;levelStart = NULL;while (current != NULL) {cout << current->val << " ";if (!levelStart) {if (current->left) levelStart = current->left;else if (current->right) levelStart = current->right;}current = current->next;}cout << "-> NULL" << endl;}
}int main() {Solution solution;Node* root = createTestTree();root = solution.connect(root);printTreeByLevel(root);  // 打印连接后的树的每一层return 0;
}