พิมพ์บรรพบุรุษร่วมของสองโหนดใน Binary Tree ใน C++

โจทย์

ให้ Binary Tree และสองโหนด ต้องการพิมพ์บรรพบุรุษร่วม (Common Ancestors) คือโหนดที่อยู่บนเส้นทางจาก Root ไปยังทั้งสองโหนด

วิธีแก้ปัญหา

1. หา Lowest Common Ancestor (LCA) ของสองโหนด
2. จาก Root ท่องหา LCA พิมพ์โหนดทั้งหมดในเส้นทาง (Ancestors ของ LCA)

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

#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;
}

struct Node* LowestCommonAncestors(struct Node* root, int n1, int n2) {
    if (root == NULL) return NULL;
    if (root->key == n1 || root->key == n2) return root;
    Node* left_lca = LowestCommonAncestors(root->left, n1, n2);
    Node* right_lca = LowestCommonAncestors(root->right, n1, n2);
    if (left_lca && right_lca) return root;
    return (left_lca != NULL) ? left_lca : right_lca;
}

bool printAncestorNodes(struct Node* root, int target) {
    if (root == NULL) return false;
    if (root->key == target) {
        cout << root->key << "\t";
        return true;
    }
    if (printAncestorNodes(root->left, target) || printAncestorNodes(root->right, target)) {
        cout << root->key << "\t";
        return true;
    }
    return false;
}

bool printcommonAncestors(struct Node* root, int first, int second) {
    struct Node* LCA = LowestCommonAncestors(root, first, second);
    if (LCA == NULL) return false;
    printAncestorNodes(root, LCA->key);
}

int main() {
    Node* root = insertNode(24);
    root->left = insertNode(8);
    root->right = insertNode(69);
    root->left->left = insertNode(12);
    root->left->right = insertNode(41);
    root->right->left = insertNode(50);
    root->right->right = insertNode(3);
    root->left->left->left = insertNode(22);
    root->right->left->left = insertNode(10);
    root->right->left->right = insertNode(6);
    if (printcommonAncestors(root, 6, 3) == false)
        cout << "No Common nodes";
    return 0;
}

ผลลัพธ์

69 24