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

각 노드에 (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() : 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): 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);
   Node nodeFive(5);
   Node nodeSeven(7);
   Node nodeTwo(2,&nodeFour,&nodeFive);
   Node nodeThree(3,NULL,&nodeSeven);
   Node nodeOne(1,&nodeTwo,&nodeThree);
   root = &nodeOne;
   Solution ob;
   root = ob.connect(root);
   printTree(root);
}

입력

[1,2,3,4,5,null,7]
Node* root;
Node nodeFour(4);
Node nodeFive(5);
Node nodeSeven(7);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,NULL,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;

출력

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