Trong bài toán này, chúng ta được cung cấp một cây nhị phân và hai nút. Nhiệm vụ của chúng ta là tạo một chương trình để Tìm khoảng cách giữa hai nút của Cây nhị phân.
Mô tả vấn đề
Chúng ta cần tìm khoảng cách giữa hai nút là số cạnh tối thiểu sẽ được duyệt khi chúng ta đi từ nút này sang nút khác.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào :cây nhị phân
Node1 =3, Node2 =5
Đầu ra :3
Giải thích
Đường dẫn từ nút 3 đến nút 5 là 3 -> 1 -> 2 -> 5. Có 3 cạnh đi ngang tạo khoảng cách 3.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng nút tổ tiên chung thấp nhất cho các nút đã cho và sau đó áp dụng công thức dưới đây,
khoảng cách (nút1, nút2) =khoảng cách (gốc, nút1) + khoảng cách (gốc, nút2) + khoảng cách (gốc, LCA)
Ví dụ
#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;
} Đầu ra
Distance between node with value 5 and node with value 3 is 3