In nút chung của hai cây BST C++

Cho hai cây tìm kiếm nhị phân (BST). In các giá trị nút xuất hiện ở cả hai cây. Sử dụng 2 stack duyệt in-order song song. So sánh đỉnh stack: bằng nhau → in, pop cả hai; nhỏ hơn → pop stack1, đi phải; lớn hơn → pop stack2, đi phải.

Duyệt in-order song song 2 stack

Giống merge 2 mảng đã sắp xếp. Độ phức tạp O(m+n) thời gian, O(h1+h2) không gian.

Ví dụ minh họa

#include <iostream>
#include <stack>
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;
}

void printCommon(Node* t1, Node* t2) {
    stack s1, s2;
    
    while (true) {
        if (t1) { s1.push(t1); t1 = t1->left; }
        else if (t2) { s2.push(t2); t2 = t2->left; }
        else if (!s1.empty() && !s2.empty()) {
            t1 = s1.top(); t2 = s2.top();
            if (t1->key == t2->key) {
                cout << t1->key << ' ';
                s1.pop(); s2.pop();
                t1 = t1->right; t2 = t2->right;
            } else if (t1->key < t2->key) {
                s1.pop(); t1 = t1->right; t2 = nullptr;
            } else {
                s2.pop(); t2 = t2->right; t1 = nullptr;
            }
        } else break;
    }
}

Node* insert(Node* root, int key) {
    if (!root) return newNode(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;
}

void inorder(Node* root) {
    if (root) { inorder(root->left); cout << root->key << ' '; inorder(root->right); }
}

int main() {
    Node *t1 = nullptr, *t2 = nullptr;
    t1 = insert(t1, 45); t1 = insert(t1, 87); t1 = insert(t1, 12);
    t1 = insert(t1, 54); t1 = insert(t1, 89); t1 = insert(t1, 19); t1 = insert(t1, 72);
    t2 = insert(t2, 72); t2 = insert(t2, 23); t2 = insert(t2, 13);
    t2 = insert(t2, 1); t2 = insert(t2, 19);
    
    cout << "Cay 1: "; inorder(t1); cout << '\n';
    cout << "Cay 2: "; inorder(t2); cout << '\n';
    cout << "Nut chung: "; printCommon(t1, t2);
    return 0;
}

Kết quả

Cay 1: 12 19 45 54 72 87 89
Cay 2: 1 13 19 23 72
Nut chung: 19 72