หาความห่างระหว่างสองโหนดของต้นไม้ไบนารีใน C++

พิจารณาว่ามีต้นไม้ไบนารีที่มีโหนดอยู่บ้าง เราต้องหาความห่างระหว่างสองโหนด u และ v สมมติว่าต้นไม้เป็นแบบด้านล่าง:

ตอนนี้ ระยะห่างระหว่าง (4, 6) = 4 ความยาวเส้นทางคือ 4 ระยะห่างระหว่าง (5, 8) = 5 เป็นต้น

เพื่อแก้ปัญหานี้ เราจะหา LCA (Lowest Common Ancestor) แล้วคำนวณระยะห่างจาก LCA ไปยังสองโหนด

ตัวอย่าง

#include <iostream> 
using namespace std; 

class Node {
public:
    int data;
    Node *left, *right;
};

Node* getNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

Node* LowestCommonAncestor(Node *root, int n1, int n2) {
    if (root == NULL)
        return root;
    if (root->data == n1 || root->data == n2)
        return root;
    Node* left = LowestCommonAncestor(root->left, n1, n2);
    Node* right = LowestCommonAncestor(root->right, n1, n2);
    if (left != NULL && right != NULL)
        return root;
    if (left != NULL)
        return LowestCommonAncestor(root->left, n1, n2);
    return LowestCommonAncestor(root->right, n1, n2);
}

int getLevel(Node *root, int k, int level) {
    if (root == NULL) return -1;
    if (root->data == k) return level;
    int left = getLevel(root->left, k, level + 1);
    if (left == -1)
        return getLevel(root->right, k, level + 1);
    return left;
}

int findDistance(Node* root, int a, int b) {
    Node* lca = LowestCommonAncestor(root, a, b);
    int dist1 = getLevel(lca, a, 0);
    int dist2 = getLevel(lca, b, 0);
    return dist1 + dist2;
}

int main() {
    Node* root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
    root->right->left = getNode(6);
    root->right->right = getNode(7);
    root->right->left->right = getNode(8);
    cout << "Distance between (4, 6) is: " << findDistance(root, 4, 6);
    cout << "\nDistance between (8, 5) is: " << findDistance(root, 8, 5);
}

ผลลัพธ์

Distance between (4, 6) is: 4
Distance between (8, 5) is: 5