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

ภาพรวมปัญหา

หาความห่างระหว่างสองโหนดในต้นไม้ไบนารี (จำนวนขอบขั้นต่ำที่ต้องเดิน)

ตัวอย่าง

Binary Tree:
       1
      / \
     2   3
    / \ /
   4  5 6

Node1 = 3, Node2 = 5
Output: 3
Path: 3 -> 1 -> 2 -> 5 (3 edges)

แนวทางแก้ปัญหา

• หา Lowest Common Ancestor (LCA) ของสองโหนด
• สูตร: Distance = Dist(root, n1) + Dist(root, n2) - 2×Dist(root, LCA)
• ใช้ Recursion หา LCA และระยะทางพร้อมกัน

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

struct Node {
    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) 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 n1, int n2, int& d1, int& d2, int& dist, int lvl) {
    if (!root) return NULL;
    if (root->key == n1) { d1 = lvl; return root; }
    if (root->key == n2) { d2 = lvl; return root; }
    
    Node* leftLCA = findDistanceRec(root->left, n1, n2, d1, d2, dist, lvl+1);
    Node* rightLCA = findDistanceRec(root->right, n1, n2, d1, d2, dist, lvl+1);
    
    if (leftLCA && rightLCA) {
        dist = d1 + d2 - 2*lvl;
        return root;
    }
    return leftLCA ? leftLCA : rightLCA;
}

int CalcNodeDistance(Node* root, int n1, int n2) {
    int d1 = -1, d2 = -1, dist;
    Node* lca = findDistanceRec(root, n1, n2, d1, d2, dist, 1);
    if (d1 != -1 && d2 != -1) return dist;
    if (d1 != -1) return calcNodeLevel(lca, n2, 0);
    if (d2 != -1) return calcNodeLevel(lca, n1, 0);
    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 3 and 5: " << CalcNodeDistance(root, 3, 5);
    return 0;
}

ผลลัพธ์

Distance between node with value 5 and node with value 3 is 3