In tổ tiên chung của hai nút trong cây nhị phân C++

Cho cây nhị phân và hai nút. In tất cả tổ tiên chung (các nút trên đường từ gốc đến LCA của hai nút). Tìm LCA (Lowest Common Ancestor) bằng đệ quy, sau đó in đường từ gốc đến LCA.

2 bước: Tìm LCA + In đường gốc→LCA

1. Hàm LCA(root, n1, n2): trả về nút chung thấp nhất.
2. Hàm printPath(root, target): in các nút trên đường từ gốc đến target.

Ví dụ minh họa

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
};

Node* newNode(int k) {
    Node* n = new Node();
    n->key = k; n->left = n->right = nullptr;
    return n;
}

Node* LCA(Node* root, int n1, int n2) {
    if (!root) return nullptr;
    if (root->key == n1 || root->key == n2) return root;
    Node* left = LCA(root->left, n1, n2);
    Node* right = LCA(root->right, n1, n2);
    if (left && right) return root;
    return left ? left : right;
}

bool printPath(Node* root, int target) {
    if (!root) return false;
    if (root->key == target) { cout << root->key << '\t'; return true; }
    if (printPath(root->left, target) || printPath(root->right, target)) {
        cout << root->key << '\t';
        return true;
    }
    return false;
}

void printCommonAncestors(Node* root, int a, int b) {
    Node* lca = LCA(root, a, b);
    if (lca) printPath(root, lca->key);
    else cout << "Khong co nut chung";
}

int main() {
    Node* root = newNode(24);
    root->left = newNode(8);
    root->right = newNode(69);
    root->left->left = newNode(12);
    root->left->right = newNode(41);
    root->right->left = newNode(50);
    root->right->right = newNode(3);
    root->left->left->left = newNode(22);
    root->right->left->left = newNode(10);
    root->right->left->right = newNode(6);
    
    printCommonAncestors(root, 6, 3);  // 69 24
    return 0;
}

Kết quả

69 24