leetcode117-populating-next-right-pointers-in-each-node-ii_level_order.cpp

#include<vector>
#include<queue>
#include<algorithm>
#include<iostream>
usingnamespacestd;
/* Definition for a Node. */
classNode {
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) {}
};

classSolution {
public:
 Node* connect(Node* root) {
if (root == nullptr)
returnnullptr;
if (root->left == nullptr && root->right == nullptr)
return root;

 queue<Node*> q;
 q.push({root}); 

while (!q.empty()) 
 {
 vector<Node*> curLevel;
for (int i = q.size(); i > 0; i--)
 {
 Node* p = q.front(); 
 q.pop(); 
 curLevel.push_back(p);
if (p->left != NULL)
 q.push(p->left);

if (p->right != NULL)
 q.push(p->right); 
 } 
int curSize = curLevel.size();
for (int i = 0; i < curSize - 1; i++) /* 设置每一层的node的next指针的指向 */
 curLevel[i]->next = curLevel[i+1];
 curLevel.back()->next = nullptr;
 }

return root; 
 }
};

// Test
intmain()
{
 Solution sol;
 Node *root = newNode(1);
 root->left = newNode(2);
 root->right = newNode(3);
 root->left->left = newNode(4);
 root->left->right = newNode(5);
 root->right->left = NULL; 
 root->right->right = newNode(7); 
 root->left->left->left = NULL;
 root->left->left->right = NULL;
 root->left->right->left = NULL;
 root->left->right->right = NULL; 
 root->right->right->left = NULL; 
 root->right->right->right = NULL; 

auto res = sol.connect(root);

return0;
}