ในปัญหานี้ เราได้รับไบนารีทรีและพอยน์เตอร์พาเรนต์ งานของเราคือค้นหาพี่น้องที่ถูกต้องของไบนารีทรีด้วยพอยน์เตอร์หลัก
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
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
