填充每个节点的下一个右侧节点指针-力扣
本题使用BFS对二叉树进行搜索,然后将每个节点的next指向右侧节点,当节点为一层的最后也给节点时,将其next指向nullptr。
/*
// 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 != nullptr){
que.push(root);
}
while(!que.empty()){
int size = que.size();
for(int i = 0; i < size; i++){
Node* cur = que.front();
que.pop();
if(i < size - 1){
cur->next = que.front();
} else{
cur->next = nullptr;
}
if(cur->left != nullptr){
que.push(cur->left);
}
if(cur->right != nullptr){
que.push(cur->right);
}
}
}
return root;
}
};
第二种写法是利用已经创建好的next指针,由于是完美二叉树,对于同一父亲节点的左右子节点,左节点的next便是右节点,而右节点的next,便是父亲节点 next节点的左子节点。
class Solution {
public:
Node* connect(Node* root) {
if(root == nullptr){
return nullptr;
}
if(root->left != nullptr){
root->left->next = root->right;
if(root->next != nullptr){
root->right->next = root->next->left;
}
}
connect(root->left);
connect(root->right);
return root;
}
};