116. 각 노드에 다음 오른쪽 포인터 채우기
설명
모든 잎이 같은 수준에 있고 모든 부모가 두 자녀를 갖는 완벽한 이진 트리가 제공됩니다. 이진 트리의 정의는 다음과 같습니다.
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
다음 오른쪽 노드를 가리키도록 각 다음 포인터를 채웁니다. 다음 오른쪽 노드가 없으면 다음 포인터를 NULL로 설정해야 합니다.
처음에는 모든 다음 포인터가 NULL로 설정됩니다.
예 1:
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
예 2:
Input: root = []
Output: []
제약:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
Input: root = []
Output: []
[0, 212 - 1] 범위에 있습니다. 1000 <= Node.val <= 1000 후속 조치:
솔루션
솔루션 1
직관
암호
/*
// 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) {
if (!root) return root;
auto node = root;
while (node->left) {
for (auto p = node; p; p = p->next) {
p->left->next = p->right;
if (p->next) p->right->next = p->next->left;
}
node = node->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) {
if (!root) return root;
auto node = root;
while (node->left) {
for (auto p = node; p; p = p->next) {
p->left->next = p->right;
if (p->next) p->right->next = p->next->left;
}
node = node->left;
}
return root;
}
}
솔루션 2
직관
스택
암호
/*
// 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) {
if (!root) return root;
queue<Node*> que;
que.push(root);
while (!que.empty()) {
int n = que.size();
Node* node;
for (int i = 0; i < n; i++) {
node = que.front();
que.pop();
if (i != n - 1)
node->next = que.front();
else
node->next = NULL;
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return root;
}
};
복잡성
유제
Reference
이 문제에 관하여(116. 각 노드에 다음 오른쪽 포인터 채우기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/jiangwenqi/116-populating-next-right-pointers-in-each-node-214n
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Reference
이 문제에 관하여(116. 각 노드에 다음 오른쪽 포인터 채우기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/116-populating-next-right-pointers-in-each-node-214n텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
