Populating Next Right Pointers in Each Node
116. Populating Next Right Pointers in Each Node
language: C++
/*
// 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) {
// return connect1(root);
return connect2(root);
}
Node* connect2(Node* root) {
if (root == nullptr)
return root;
Node* value;
queue<Node*> q;
q.push(root);
int size = 0;
while (!q.empty()) {
size = q.size();
for (int i = 0; i < size; i++) {
value = q.front();
q.pop();
if (i < size - 1)
value->next = q.front();
if (value->left)
q.push(value->left);
if (value->right)
q.push(value->right);
}
}
return root;
}
Node* connect1(Node* root) {
if (root == nullptr)
return root;
Node* leftmost = root;
while(leftmost->left != nullptr) {
Node* head = leftmost;
while (head != nullptr) {
head->left->next = head->right;
if (head->next != nullptr) {
head->right->next = head->next->left;
}
head = head->next;
}
leftmost = leftmost->left;
}
return root;
}
};
시도
/*
// 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) {
return helper(root);
}
Node* helper(Node* root) {
Node* value;
Node* prevNode = nullptr;
int idx = 0;
queue<Node*> q;
q.push(root);
while(!q.empty()) {
value = q.front();
q.pop();
if (prevNode != nullptr && prevNode->val != value->val)
value->next = prevNode;
if (value->left)
q.push(value->left);
if (value->right)
q.push(value->right);
prevNode = value->left;
}
return root;
}
};이러면 right child 만 안나온다
fail test case
Your input : [1,2,3,4,5,6,7]
Output : [1,#,2,#,4,6,#]
Expected : [1,#,2,3,#,4,5,6,7,#]
그래서 조금 고쳤는데
class Solution {
public:
Node* connect(Node* root) {
return helper(root);
}
Node* helper(Node* root) {
Node* value;
Node* valueTemp;
Node* prevNode = nullptr;
queue<Node*> qTemp;
queue<Node*> q;
q.push(root);
qTemp.push(nullptr);
while(!q.empty()) {
value = q.front();
q.pop();
//if (prevNode != nullptr && prevNode->val != value->val)
// value->next = prevNode;
if (value->left) {
q.push(value->left);
qTemp.push(value->left);
}
if (value->right) {
q.push(value->right);
qTemp.push(value->right);
qTemp.push(nullptr);
}
// if (prevNode->val != value->val)
// prevNode = value->left;
valueTemp = qTemp.front();
qTemp.pop();
value->next = valueTemp;
if (valueTemp != nullptr && valueTemp->val == value->val) {
valueTemp = qTemp.front();
qTemp.pop();
value->next = valueTemp;
}
}
return root;
}
};Your input : [1,2,3,4,5,6,7]
Output : [1,#,2,3,#,4,5,#]
Expected : [1,#,2,3,#,4,5,6,7,#]
조금만 고쳐졌다..;
class Solution {
public:
Node* connect(Node* root) {
return helper(root);
}
Node* helper(Node* root) {
Node* value;
Node* valueTemp;
// Node* prevNode = nullptr;
queue<Node*> qTemp;
queue<Node*> q;
int level = 0;
q.push(root);
qTemp.push(nullptr);
while(!q.empty()) {
value = q.front();
q.pop();
//if (prevNode != nullptr && prevNode->val != value->val)
// value->next = prevNode;
if (value->left) {
q.push(value->left);
qTemp.push(value->left);
}
if (value->right) {
q.push(value->right);
qTemp.push(value->right);
qTemp.push(nullptr);
}
if (value->left || value->right)
level++;
// if (prevNode->val != value->val)
// prevNode = value->left;
valueTemp = qTemp.front();
qTemp.pop();
value->next = valueTemp;
if (valueTemp != nullptr && valueTemp->val == value->val) {
valueTemp = qTemp.front();
qTemp.pop();
value->next = valueTemp;
}
if (value->next == nullptr) {
level--;
}
if (value->next == nullptr && level > 1) {
valueTemp = qTemp.front();
qTemp.pop();
value->next = valueTemp;
}
/*
if (qTemp.size() > 1) {
valueTemp = qTemp.front();
qTemp.pop();
value->next = valueTemp;
}
*/
}
return root;
}
};현재 레벨을 가지고 어떻게 해보려고 했는데 항상 5 다음이 문제였다;
노드의 level 에 따라서 nullptr 을 만났을 때 면제권? 한 번 더 qTemp 의 다음으로 가리키도록 하는 것을 줘야겠다고 생각이 들었는데,
그러면 각 노드마다 자신의 level 을 기록해놔야하는데 더 쉬운 방법이 없을까 생각했었다. 시간 많이 지나서 걍 솔루션 고고
문제점
와 솔루션보고 그래도 생각하는 게 조금 는 게 느껴졌다?
일단 처음 문제 보고 아 level order traversal 이구나 알아서 queue 를 써야겠네? 생각하고 -> 1학기에 자료구조를 들었으니까... 기억력;
전 노드를 저장해 놓고 그 다음 노드에서 그 전 노드를 저장하면 되는 거 아닌가? 생각하다가
현재 노드에서 다음 노드를 저장해놓으면 되는 거 아닌가? 큐에 있을텐데.. 생각도 하고
level 을 사용하면 될 것 같은데? 근데 이러면 다시 다 저장해야되는 거 아니야? 생각했다
솔루션 보니까 두 가지 방법이 있었는데 하 생각했던 거 있어서 진짜 이렇게라도 조금이나마 나를 칭찬하면서 참고했다..
1) leftmost 를 두고 사용하며, 현재 노드에 연결시키는 방법
leftmost 노드를 저장해놓고, head를 두고, head 에서
leftmost.left != nullptr 로 멈추는 조건을 걸어놓고
2) level 을 가지고 하는 방법
level을 가지고 해야겠다는 생각은 했었는데 다시 다른 자료구조에 넣어서 해야되나 생각했었는데
현재 큐의 사이즈를 가지고 i < size - 1 이것으로 rightmost 한 노드를 제외하고 next 에 연결시킬 수 있었다.
아 진짜 풀 수 있었는데~~~~~~(못 풀었을테지만) ㅋㅋㅋㅋㅋㅋㅋㅋ 하면서 기쁜 마음으로 솔루션 보면서 소스 수정했다