ในปัญหานี้ เราได้รับไบนารีทรีและสองโหนดของไบนารีทรีถูกกำหนด และเราต้องพิมพ์บรรพบุรุษร่วมทั้งหมดของโหนด นั่นคือ โหนดทั่วไปที่เกิดขึ้นในเส้นทางจากการข้ามผ่านจากรูทไปยังโหนด
ต้นไม้ไบนารี เป็นต้นไม้พิเศษที่ทุกโหนดมีโหนดย่อยสูงสุดสองโหนด ดังนั้น ทุกโหนดจึงเป็นโหนดปลายสุดหรือมีโหนดย่อยหนึ่งหรือสองโหนด
ตัวอย่าง
โหนดบรรพบุรุษ เป็นโหนดที่เชื่อมต่อกับโหนดระดับล่างในทรี
โหนดบรรพบุรุษร่วมกัน ของสองโหนดคือโหนดที่เป็นโหนดบรรพบุรุษของทั้งสองโหนดในทรี
ตัวอย่างเช่น − 
ในต้นไม้ไบนารีด้านบน เราต้องหาบรรพบุรุษร่วมของ 0 และ 6
ผลผลิต − 3, 2
จากปัญหานี้ มาสร้างอัลกอริทึมสำหรับแก้ปัญหานี้
อัลกอริทึม
Step 1 : Find the lowest common ancestor of the two nodes of the given tree. And print it. Step 2 : Traverse upward to the root node and print all the nodes that come in the path.
ตัวอย่าง
ตอนนี้ มาสร้างโปรแกรมเพื่อแสดงวิธีแก้ปัญหานี้กัน
#include <iostream>
using namespace std;
struct Node {
struct Node* left, *right;
int key;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
struct Node* LowestCommonAncestors(struct Node* root, int n1, int n2){
if (root == NULL)
return NULL;
if (root->key == n1 || root->key == n2)
return root;
Node* left_lca = LowestCommonAncestors(root->left, n1, n2);
Node* right_lca = LowestCommonAncestors(root->right, n1, n2);
if (left_lca && right_lca)
return root;
return (left_lca != NULL) ? left_lca : right_lca;
}
bool printAncestorNodes(struct Node* root, int target){
if (root == NULL)
return false;
if (root->key == target) {
cout << root->key << "\t";
return true;
}
if (printAncestorNodes(root->left, target) ||
printAncestorNodes(root->right, target)) {
cout << root->key << "\t”;
return true;
}
return false;
}
bool printcommonAncestors(struct Node* root, int first, int second){
struct Node* LCA = LowestCommonAncestors(root, first, second);
if (LCA == NULL)
return false;
printAncestorNodes(root, LCA->key);
}
int main(){
Node* root = insertNode(24);
root->left = insertNode(8);
root->right = insertNode(69);
root->left->left = insertNode(12);
root->left->right = insertNode(41);
root->right->left = insertNode(50);
root->right->right = insertNode(3);
root->left->left->left = insertNode(22);
root->right->left->left = insertNode(10);
root->right->left->right = insertNode(6);
if (printcommonAncestors(root, 6, 3) == false)
cout << "No Common nodes";
return 0;
} ผลลัพธ์
69 24
