C++LeetCode 구현(117.각 노드 의 오른쪽 포인터 2)

[LeetCode]117.Populating Next Right Pointers in Each Node II 각 노드 의 오른쪽 포인터 2
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *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.
Follow up:

You may only use constant extra space.

Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above 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.
Constraints:

The number of nodes in the given tree is less than 6000.

-100 <= node.val <= 100

이것 은 이전의 저것 이다  Populating Next Right Pointers in Each Node  의 연속 은 원래 의 완전 이 진 트 리 의 조건 이 만족 하지 않 지만 전체적인 사고방식 은 비슷 하고 귀속 과 비 귀속 의 해법 이 있다.우 리 는 먼저 재 귀적 인 해법 을 살 펴 보 자.여 기 는 나무 가 부족 할 수 있 기 때문에 부모 노드 와 같은 층 의 노드 를 평행 으로 스 캔 하여 그들의 좌우 부분 을 찾 아야 한다.코드 는 다음 과 같 습 니 다:
해법 1:

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return NULL;
        Node *p = root->next;
        while (p) {
            if (p->left) {
                p = p->left;
                break;
            }
            if (p->right) {
                p = p->right;
                break;
            }
            p = p->next;
        }
        if (root->right) root->right->next = p; 
        if (root->left) root->left->next = root->right ? root->right : p; 
        connect(root->right);
        connect(root->left);
        return root;
    }
};

재 귀적 이지 않 은 방법 에 대해 저 는 놀 라 운 발견 전의 방법 을 직접 사용 할 수 있 고 수정 할 필요 가 없습니다.알고리즘 사고방식 은 이전의 블 로 그 를 참조 할 수 있 습 니 다.  Populating Next Right Pointers in Each Node코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return NULL;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int len = q.size();
            for (int i = 0; i < len; ++i) {
                Node *t = q.front(); q.pop();
                if (i < len - 1) t->next = q.front();
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return root;
    }
};

위의 두 가지 방법 은 모두 OJ 를 통과 할 수 있 지만 사실은 문제 의 요구 에 부합 되 지 않 습 니 다.제목 은 constant space 만 사용 할 수 있다 고 했 지만 OJ 는 space 사용 상황 을 전문 적 으로 검사 하 는 test 를 쓰 지 않 았 습 니 다.그러면 아래 에 constant space 의 해법 을 붙 입 니 다.이 해법 도 층 차 를 옮 겨 다 니 는 것 입 니 다.다만 quue 를 사용 하지 않 았 습 니 다.우 리 는 Dummy 결점 을 만들어 서 각 층 의 첫 번 째 결점 의 앞 결점 을 가리 키 고 지침 cur 는 이 층 을 옮 겨 다 니 는 데 사용 합 니 다.여 기 는 실제 적 으로 한 층 을 옮 겨 다 니 고 다음 층 의 next 를 연결 합 니 다.먼저 뿌리 결점 부터 시작 합 니 다.만약 에 왼쪽 결점 이 존재 한다 면 cur 의 next 는 왼쪽 결점 을 연결 한 다음 에 cur 는 next 지침 을 가리 킵 니 다.루트 의 오른쪽 점 이 존재 한다 면 cur 의 next 는 오른쪽 점 을 연결 한 다음 cur 는 next 지침 을 가리킨다.이때 root 의 좌우 자 결점 이 연결 되 어 있 습 니 다.이때 root 는 오른쪽으로 한 자 리 를 옮 겨 next 지침 을 가리 키 고 있 습 니 다.이때 root 가 존재 하지 않 는 다 면 현재 층 이 이미 옮 겨 다 녔 음 을 의미 합 니 다.cur 를 Dummy 결점 으로 초기 화 합 니 다.root 는 이때 dummy->next 입 니 다.즉,다음 층 의 첫 번 째 결점 입 니 다.그리고 Dummy 의 next 지침 을 비 우거 나 cur 의 next 지침 을 비 울 수도 있 습 니 다.앞 에 cur 를 dummy 로 대 입 했 기 때 문 입 니 다.그럼 지금 생각해 보 세 요.왜 비 웠 나 요?Dummy 를 사용 하 는 목적 은 다음 줄 의 첫 번 째 노드 의 위 치 를 가리 키 는 것 입 니 다.즉,dummy->next 입 니 다.루트 를 dummy->next 로 할당 한 후에 이 Dummy 의 사명 은 이미 완성 되 었 습 니 다.끊 어야 합 니 다.계속 열 리 면 현재 root 가 엽 결 점 이 라 고 가정 하면 while 순환 은 실 행 될 것 입 니 다.앞의 두 if 에 들 어가 지 않 을 것 입 니 다.그리고 루트 가 오른쪽으로 이동 하면 마지막 if 에 들 어 갑 니 다.그 전에 dummy->next 를 끊 지 않 았 다 면 루트 는 이전의 잎 결점 을 가리 키 고 순환 이 생 겨 무릎 을 꿇 었 습 니 다.그 러 니까 비 워.
여기 서 다음 Dummy 결점 은 어떻게 각 층 의 첫 번 째 결점 의 앞 점 을 가리 키 는 지,과정 은 이 렇 습 니 다.Dummy 는 새로운 결점 을 만 드 는 것 입 니 다.그 목적 은 root 결점 의 다음 층 의 첫 번 째 결점 의 앞 점 을 가리 키 는 것 입 니 다.구체 적 으로 이렇게 하 는 것 입 니 다.주로 cur 지침 에 의 해 먼저 cur 는 Dummy 를 가리 키 는 것 입 니 다.그리고 cur 는 루트 아래 층 의 첫 번 째 결점 을 연결 하면 Dummy 도 연 결 됩 니 다.그리고 루트 층 이 다 옮 겨 다 니 면 루트 는 한 층 아래로 이동 해 야 합 니 다.이렇게 하면 Dummy 노드 가 끝 난 후에 연 결 된 위 치 는 바로 루트 에 할당 되 었 습 니 다.그리고 cur 는 Dummy,Dummy 를 가리 키 고 끊 어야 합 니 다.이렇게 하면 다시 초기 상태 로 돌아 가 왕복 하면 모두 연 결 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 3: 

class Solution {
public:
    Node* connect(Node* root) {
        Node *dummy = new Node(-1), *cur = dummy, *head = root;
        while (root) {
            if (root->left) {
                cur->next = root->left;
                cur = cur->next;
            }
            if (root->right) {
                cur->next = root->right;
                cur = cur->next;
            }
            root = root->next;
            if (!root) {
                cur = dummy;
                root = dummy->next;
                dummy->next = NULL;
            }
        }
        return head;
    }
};

유사 한 제목:
Populating Next Right Pointers in Each Node
참고 자료:
https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/37813/java-solution-with-constant-space
https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/37828/o1-space-on-complexity-iterative-solution
C++구현 LeetCode(117.각 노드 의 오른쪽 포인터 2)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 각 노드 의 오른쪽 포인터 2 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많이 응원 해 주세요!