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

116. 填充每个节点的下一个右侧节点指针——广度搜索、队列

本文主要是介绍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;}
};