ในปัญหานี้ เราได้รับไบนารีทรีและสองโหนด งานของเราคือการสร้างโปรแกรมเพื่อค้นหาระยะห่างระหว่างสองโหนดของไบนารีทรี
คำอธิบายปัญหา
เราจำเป็นต้องหาระยะห่างระหว่างโหนดสองโหนดซึ่งเป็นจำนวนขอบขั้นต่ำที่จะข้ามเมื่อเราเปลี่ยนจากโหนดหนึ่งไปอีกโหนดหนึ่ง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล :ต้นไม้ไบนารี
Node1 =3 ,Node2 =5
ผลผลิต :3
คำอธิบาย
เส้นทางจากโหนด 3 ไปยังโหนด 5 คือ 3 -> 1 -> 2 -> 5. มี 3 ขอบที่ขวางซึ่งทำให้เกิดระยะห่าง 3
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการใช้โหนดบรรพบุรุษร่วมที่ต่ำที่สุดสำหรับโหนดที่กำหนด จากนั้นใช้สูตรด้านล่าง
Distance(node1, node2) =ระยะทาง (root, node1) + ระยะทาง (root, node2) + ระยะทาง (root, LCA)
ตัวอย่าง
#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;
}
int calcNodeLevel(Node *root, int val, int level) {
if (root == NULL)
return -1;
if (root->key == val)
return level;
int lvl = calcNodeLevel(root->left, val, level+1);
return (lvl != -1)? lvl : calcNodeLevel(root->right, val, level+1);
}
Node *findDistanceRec(Node* root, int node1, int node2, int &dist1, int &dist2, int &dist, int lvl){
if (root == NULL) return NULL;
if (root->key == node1){
dist1 = lvl;
return root;
}
if (root->key == node2){
dist2 = lvl;
return root;
}
Node *leftLCA = findDistanceRec(root->left, node1, node2, dist1,dist2, dist, lvl+1);
Node *rightLCA = findDistanceRec(root->right, node1, node2, dist1,dist2, dist, lvl+1);
if (leftLCA && rightLCA){
dist = dist1 + dist2 - 2*lvl;
return root;
}
return (leftLCA != NULL)? leftLCA: rightLCA;
}
int CalcNodeDistance(Node *root, int node1, int node2) {
int dist1 = -1, dist2 = -1, dist;
Node *lca = findDistanceRec(root, node1, node2, dist1, dist2, dist, 1);
if (dist1 != -1 && dist2 != -1)
return dist;
if (dist1 != -1){
dist = calcNodeLevel(lca, node2, 0);
return dist;
}
if (dist2 != -1){
dist = calcNodeLevel(lca, node1, 0);
return dist;
}
return -1;
}
int main(){
Node * root = insertNode(1);
root->left = insertNode(2);
root->right = insertNode(3);
root->left->left = insertNode(4);
root->left->right = insertNode(5);
root->right->left = insertNode(6);
cout<<"Distance between node with value 5 and node with value 3 is"<<CalcNodeDistance(root, 3, 5);
return 0;
} ผลลัพธ์
Distance between node with value 5 and node with value 3 is 3
