C++ Truy vấn DFS của cây con trong cây

Cho cây nhị phân, thực hiện DFS từ một nút cho trước (coi nút đó là gốc của cây con).

Ví dụ: DFS từ nút F.

Áp dụng phương pháp tiền xử lý để giảm độ phức tạp, tránh chạy DFS riêng cho mỗi truy vấn.

Phương pháp giải

Thực hiện DFS một lần từ gốc cây thật, lưu thứ tự duyệt vào mảng a[] và số nút trong cây con của mỗi nút vào nodesunder[]. Dùng map mape lưu chỉ số của mỗi nút trong mảng DFS. Khi truy vấn nút u, in các phần tử từ a[mape[u]] đến a[mape[u] + nodesunder[u] - 1].

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

#define N 100000
vector<int> v[N];
unordered_map<int, int> mape;
vector<int> a;

void dfs(int nodesunder[], int child, int parent) {
    a.push_back(child);
    nodesunder[child] = 1;
    for (auto it : v[child]) {
        if (it != parent) {
            dfs(nodesunder, it, child);
            nodesunder[child] += nodesunder[it];
        }
    }
}

void printDFS(int node, int nodesunder[]) {
    int ind = mape[node];
    cout << "DFS của cây con " << node << ": ";
    for (int i = ind; i < ind + nodesunder[node]; i++)
        cout << a[i] << " ";
    cout << endl;
}

void addEdge(int x, int y) {
    v[x].push_back(y);
    v[y].push_back(x);
}

void mark() {
    for (int i = 0; i < (int)a.size(); i++)
        mape[a[i]] = i;
}

int main() {
    int n = 7;
    addEdge(1, 2); addEdge(1, 3);
    addEdge(2, 4); addEdge(2, 5);
    addEdge(4, 6); addEdge(4, 7);

    int nodesunder[n+1];
    dfs(nodesunder, 1, 0);
    mark();

    printDFS(2, nodesunder);
    printDFS(4, nodesunder);
    return 0;
}

Kết quả

DFS của cây con 2: 2 4 6 7 5
DFS của cây con 4: 4 6 7

Giải thích

Tiền tính thứ tự DFS và kích thước cây con. Truy vấn chỉ cần cắt đoạn mảng đã tính sẵn, độ phức tạp O(1) mỗi truy vấn sau O(N) tiền xử lý.

Kết luận

Đã giải bài toán truy vấn DFS cây con bằng tiền xử lý DFS một lần. Code C++ có thể viết bằng Java, Python, C. Hy vọng hữu ích.