C++의 각 노드에 다음 오른쪽 포인터 채우기

각 노드에 (data, left, right, next) 필드가 있는 완전한 이진 트리가 있다고 가정합니다. 왼쪽은 왼쪽 하위 트리를 가리키고 오른쪽은 오른쪽 하위 트리를 가리키고 다음 포인터는 다음 노드를 가리킵니다. . 오른쪽에 노드가 없으면 null이 됩니다. 따라서 처음에는 다음 포인터 각각이 null로 설정되어 있으므로 링크를 만들어야 합니다. 트리가 첫 번째 노드와 같다고 가정하면 다음 노드로 변환됩니다 -

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• pre :=root, nextPre :=null 및 prev :=null로 설정
• pre가 null이 아닌 동안
  • pre가 null이 아닌 동안
    • pre의 왼쪽이 null이 아닌 경우
      • set next of prev :=pre의 왼쪽, prev가 null이 아닐 때, 그렇지 않으면 nextPre :=pre의 왼쪽
      • prev :=pre의 왼쪽
    • pre의 권한이 null이 아닌 경우
      • prev의 다음 설정 :=prev가 null이 아닐 때 pre의 오른쪽, 그렇지 않으면 nextPre :=pre의 오른쪽
      • prev :=pre의 오른쪽
  • pre :=nextPre
  • nextPre를 null로 설정하고 prev를 null로 설정
• null 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
#include <stack>
using namespace std;
class Node {
public:
   int val;
   Node* left;
   Node* right;
   Node* next;
   Node() {}
   Node(int _val, Node* _left, Node* _right) {
      val = _val;
      left = _left;
      right = _right;
      next = NULL;
   }
};
class Solution {
public:
   Node* connect(Node* root) {
      Node* pre = root;
      Node* nextPre = NULL;
      Node* prev = NULL;
      while(pre){
         while(pre){
            //cout << pre->val << endl;
            if(pre->left){
               if(prev){
                  prev->next = pre->left;
               }else{
                  nextPre = pre->left;
               }
               prev = pre->left;
            }
            if(pre->right){
               if(prev){
                  prev->next = pre->right;
               }else{
                  nextPre = pre->right;
               }
               prev = pre->right;
            }
            pre = pre->next;
         }
         //cout << "*" << endl;
         pre = nextPre;
         nextPre = NULL;
         prev = NULL;
      }
      return root;
   }
};
void printTree(Node* root) {
   cout << "[";
   if (root == NULL) return;
   queue<Node*> q;
   Node *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      }
      else {
         // if(curr->next)
         // q.push(curr->next);
         if(curr->left)
            q.push(curr->left);
            if(curr->right)
               q.push(curr->right);
               if(curr->val == 0){
                  cout << "null" << ", ";
               }else{
                  cout << curr->val << ", ";
                  if (curr->next == NULL) cout<<"#, ";
              }
      }
   }
   cout << "]"<<endl;
}
int main() {
Node* root;
Node nodeFour(4, NULL, NULL);
Node nodeFive(5, NULL, NULL );
Node nodeSeven(7, NULL, NULL);
Node nodeSix(6, NULL, NULL);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,&nodeSix,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;
Solution ob;
root = ob.connect(root);
printTree(root);
}

입력

[1,2,3,4,5,6,7]
Node* root;
Node nodeFour(4, NULL, NULL);
Node nodeFive(5, NULL, NULL );
Node nodeSeven(7, NULL, NULL);
Node nodeSix(6, NULL, NULL);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,&nodeSix,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;
Solution ob;
root = ob.connect(root);

출력

[1, #, 2, 3, #, 4, 5, 6, 7, #, ]