C++에서 부모 포인터가 있는 이진 트리의 오른쪽 형제 찾기

이 문제에서는 이진 트리와 부모 포인터가 제공됩니다. 우리의 임무는 부모 포인터가 있는 이진 트리의 오른쪽 형제를 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

Node = 3

출력

7

솔루션 접근 방식

문제에 대한 간단한 해결책은 현재 노드와 동일한 수준에 있는 가장 가까운 조상(현재 노드도 현재 노드의 가장 가까운 노드도 아님)의 리프 노드를 찾는 것입니다. 이것은 올라갈 때 레벨을 세고 내려올 때 레벨을 세어 수행됩니다. 그런 다음 노드를 찾습니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node *left, *right, *parent;
};
Node* newNode(int item, Node* parent) {
   Node* temp = new Node;
   temp->data = item;
   temp->left = temp->right = NULL;
   temp->parent = parent;
   return temp;
}
Node* findRightSiblingNodeBT(Node* node, int level) {
   if (node == NULL || node->parent == NULL)
      return NULL;
   while (node->parent->right == node ||
      (node->parent->right == NULL && node->parent->left == node)) {
         if (node->parent == NULL || node->parent->parent == NULL)
            return NULL;
      node = node->parent;
      level++;
   }
   node = node->parent->right;
   if (node == NULL)
      return NULL;
   while (level > 0) {
      if (node->left != NULL)
         node = node->left;
      else if (node->right != NULL)
         node = node->right;
      else
         break;
      level--;
   }
   if (level == 0)
      return node;
   return findRightSiblingNodeBT(node, level);
}
int main(){
   Node* root = newNode(4, NULL);
   root->left = newNode(2, root);
   root->right = newNode(5, root);
   root->left->left = newNode(1, root->left);
   root->left->left->left = newNode(9, root->left->left);
   root->left->left->left->left = newNode(3, root->left->left->left);
   root->right->right = newNode(8, root->right);
   root->right->right->right = newNode(0, root->right->right);
   root->right->right->right->right = newNode(7, root->right->right->right);
   Node * currentNode = root->left->left->left->left;
   cout<<"The current node is "<<currentNode->data<<endl;
   Node* rightSibling = findRightSiblingNodeBT(currentNode, 0);
   if (rightSibling)
      cout<<"The right sibling of the current node is "<<rightSibling->data;
   else
      cout<<"No right siblings found!";
   return 0;
}

출력

The current node is 3
The right sibling of the current node is 7