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