本文主要是介绍116. 填充每个节点的下一个右侧节点指针——广度搜索、队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
方法一 使用队列
class Solution {
public:Node* connect(Node* root) {if(!root)return root;queue<Node*> que;Node* ptr = root;que.push(root);while(!que.empty()){int size = que.size();Node *left = que.front(); //先获取每层最左侧的节点if(left -> left) //左孩子存在放入队列que.push(left -> left);if(left -> right) //右孩子存在放入队列que.push(left -> right);que.pop(); //推出for(int i = 1; i < size; i++){ //逐个对右侧节点进行操作Node *right = que.front(); //获取节点left -> next = right; //left的next 指向 rightleft = right; //left向右侧移动if(left -> left) //左孩子存在放入队列que.push(left -> left);if(left -> right) //右孩子存在放入队列que.push(left -> right);que.pop();}}return root;}
};
Accepted
59/59 cases passed (16 ms)
Your runtime beats 87.17 % of cpp submissions
Your memory usage beats 30.81 % of cpp submissions (16.7 MB)
方法二 空间复杂度O(1)
class Solution {
public:Node* connect(Node* root) {if(!root)return root;Node* leftAlways = root;while(leftAlways -> left){ //如果左节点存在Node* ptr = leftAlways;while(ptr){ptr -> left -> next = ptr -> right; //左节点的next 指向 右节点if(ptr -> next){ //如果当前节点的next存在ptr -> right -> next = ptr -> next -> left; //右节点的next 指向 当前节点的next节点的左节点}ptr = ptr -> next; //进入next节点继续操作}leftAlways = leftAlways -> left; //leftAlways始终是每一层的最左节点}return root;}
};
Accepted
59/59 cases passed (20 ms)
Your runtime beats 59.29 % of cpp submissions
Your memory usage beats 94.83 % of cpp submissions (16.3 MB)
这篇关于116. 填充每个节点的下一个右侧节点指针——广度搜索、队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
