Cho cây nhị phân và hai nút u, v. Tìm khoảng cách (số cạnh) giữa u và v.
Ví dụ
Cây: 1
/ \
2 3
/ \ /
4 5 6
u=3, v=5 → Đường đi: 3-1-2-5 → Khoảng cách = 3
Phương pháp: LCA (Lowest Common Ancestor)
dist(u, v) = dist(root, u) + dist(root, v) - 2 * dist(root, LCA(u, v))
Cần hàm tìm LCA và hàm tính độ sâu/độ dài đường đi từ gốc.
Chương trình C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int d) : data(d), left(nullptr), right(nullptr) {}
};
Node* findLCA(Node* root, int u, int v) {
if (!root) return nullptr;
if (root->data == u || root->data == v) return root;
Node* leftLCA = findLCA(root->left, u, v);
Node* rightLCA = findLCA(root->right, u, v);
if (leftLCA && rightLCA) return root;
return leftLCA ? leftLCA : rightLCA;
}
int findLevel(Node* root, int val, int level) {
if (!root) return -1;
if (root->data == val) return level;
int left = findLevel(root->left, val, level+1);
if (left != -1) return left;
return findLevel(root->right, val, level+1);
}
int findDistance(Node* root, int u, int v) {
Node* lca = findLCA(root, u, v);
int d1 = findLevel(lca, u, 0);
int d2 = findLevel(lca, v, 0);
return d1 + d2;
}
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
cout << "Khoang cach (3, 5) = " << findDistance(root, 3, 5) << endl; // 3
return 0;
}