Leetcode | Populating Next Right Pointers in Each Node I & II
16480 단어 LeetCode
Populating Next Right Pointers in Each Node I
Given a binary tree
struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; }Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).For example,Given the following perfect binary tree, 1/\2 3/\/\4 5 6 7After calling your function, the tree should look like: 1 -> NULL/\2 -> 3 -> NULL/\/\4->5->6->7 -> NULL
Method I
여기에서 나는 bfs의 방법을 사용하거나 차원을 두루 훑어보라고 한다.
1 class Solution {
2 public:
3 void connect(TreeLinkNode *root) {
4 if (root == NULL) {
5 return;
6 }
7 queue<TreeLinkNode*> q;
8 TreeLinkNode* p, *endOfLayer;
9 q.push(root);
10 endOfLayer = root;
11
12 while (!q.empty()) {
13 p = q.front();
14 q.pop();
15
16 if (p->left) q.push(p->left);
17 if (p->right) q.push(p->right);
18 if (p == endOfLayer) {
19 p->next = NULL;
20 endOfLayer = q.back();
21 } else {
22 p->next = q.front();
23 }
24 }
25 }
26 };
Method II
인터넷의 또 다른 방법은next라는 바늘을 이용한 것이다.k층에 접근할 때 k+1층의next 바늘을 설정합니다.각 층의 시작은front 바늘로 표시하고, 현재 층의 현재 결점은cur로 표시하며, 다음 층의 선행 결점은next로 표시합니다.넥스트가 비어 있을 때 다음 층의 첫 번째 결점임을 표시하고 특수 처리해야 합니다.
pefect binary tree이기 때문에 다음 층으로 들어가면front=front->left;
이런 방법의 장점은 여전히 차원이 두루 흐르는 사상이지만queue, O(1)의 공간을 사용하지 않았다는 것이다.
1 class Solution {
2 public:
3 void connect(TreeLinkNode *root) {
4 if (root == NULL) {
5 return;
6 }
7
8 TreeLinkNode *cur, *front, *next;
9 front = cur = root;
10 next = NULL;
11
12 while (front != NULL) {
13 if (cur->left != NULL) {
14 if (next == NULL) {
15 next = cur->left;
16 } else {
17 next->next = cur->left;
18 next = next->next;
19 }
20 }
21 if (cur->right != NULL) {
22 if (next == NULL) {
23 next = cur->right;
24 } else {
25 next->next = cur->right;
26 next = next->next;
27 }
28 }
29 cur = cur->next;
30 if (cur == NULL) {
31 front = front->left;
32 cur = front;
33 next = NULL;
34 }
35 }
36 }
37 };
Method III
물론 귀속으로도 가능하다.직관적이기도 하고.
class Solution {
public:
void connect(TreeLinkNode *root) {
if (root == NULL) {
return;
}
if (root->left) {
root->left->next = root->right;
}
if (root->right && root->next) {
root->right->next = root->next->left;
}
connect(root->left);
connect(root->right);
}
};
Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
O (1) 공간을 요구하는 이상queue (Method I) 와 귀환 (Method III) 을 사용하면 안 된다.
여기는 임의의binarytree이기 때문에 다음 층의 헤더 바늘을 유지해야 합니다.cur가 비어 있을 때 다음 층의 헤더 포인터를 가리키며 비어 있으면 종료합니다.그래서 순환 조건은cur!=NULL.
1 class Solution {
2 public:
3 void connect(TreeLinkNode *root) {
4 if (root == NULL) {
5 return;
6 }
7
8 TreeLinkNode *cur, *nextFront, *next;
9 cur = root;
10 nextFront = next = NULL;
11
12 while (cur != NULL) {
13 if (cur->left != NULL) {
14 if (next == NULL) {
15 nextFront = next = cur->left;
16 } else {
17 next->next = cur->left;
18 next = next->next;
19 }
20 }
21 if (cur->right != NULL) {
22 if (next == NULL) {
23 nextFront = next = cur->right;
24 } else {
25 next->next = cur->right;
26 next = next->next;
27 }
28 }
29 cur = cur->next;
30 if (cur == NULL) {
31 cur = nextFront;
32 nextFront = next = NULL;
33 }
34 }
35 }
36 };
세 번째 브러시를 할 때 코드가 많이 간결해졌다.
1 void connect(TreeLinkNode *root) {
2 TreeLinkNode h(0), *p = root, *next;
3
4 while (p) {
5 next = &h;
6 h.next = NULL;
7 for (; p; p = p->next) {
8 if (p->left) {
9 next->next = p->left;
10 next = next->next;
11 }
12 if (p->right) {
13 next->next = p->right;
14 next = next->next;
15 }
16 }
17 p = h.next;
18 }
19 }
I와 II의 코드는 일치한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.