ツリー内のサブツリーのDFSに対するC++クエリ

この問題では、バイナリツリーが与えられ、特定のノードからdfsを実行する必要があります。このノードでは、指定されたノードをルートとして想定し、そこからdfsを実行します。

上記のツリーで、ノードFからDFSを実行する必要があると仮定します

このチュートリアルでは、いくつかの非正統的な方法を適用して、時間計算量を大幅に削減し、より高い制約に対してもこのコードを実行できるようにします。

アプローチ −このアプローチでは、単純な方法ではありません。つまり、より高い制約では機能しないため、すべてのノードにdfsを適用するだけなので、TLEの取得を回避するためにいくつかの非正統的な方法を使用しようとします。

#include <bits/stdc++.h>
using namespace std;
#define N 100000
// Adjacency list to store the
// tree nodes connections
vector<int> v[N];
unordered_map<int, int> mape; // will be used for associating the node with it's index
vector<int> a;
void dfs(int nodesunder[], int child, int parent){ // function for dfs and     precalculation our nodesunder
    a.push_back(child); // storing the dfs of our tree
    // nodesunder of child subtree
    nodesunder[child] = 1;
    for (auto it : v[child]) { // performing normal dfs

        if (it != parent) { // as we the child can climb up to
        //it's parent so we are trying to avoid that as it will become a cycle
            dfs(nodesunder, it, child); // recursive call
            nodesunder[child] += nodesunder[it]; // storing incrementing the nodesunder
        //by the number of nodes under it's children
        }
    }
}
// Function to print the DFS of subtree of node
void printDFS(int node, int nodesunder[]){
    int ind = mape[node]; // index of our node in the dfs array
    cout << "The DFS of subtree " << node << ": ";
    // print the DFS of subtree
    for (int i = ind; i < ind + nodesunder[node]; i++){ // going through dfs array and then
    //printing all the nodes under our given node
        cout << a[i] << " ";
    }
    cout << endl;
}
void addEdgetoGraph(int x, int y){ // for maintaining adjacency list
    v[x].push_back(y);
    v[y].push_back(x);
}
void mark(){ // marking each node with it's index in dfs array
    int size = a.size();
    // marks the index
    for (int i = 0; i < size; i++) {
       mape[a[i]] = i;
    }
}
int main(){
    int n = 7;
    // add edges of a tree
    addEdgetoGraph(1, 2);
    addEdgetoGraph(1, 3);
    addEdgetoGraph(2, 4);
    addEdgetoGraph(2, 5);
    addEdgetoGraph(4, 6);
    addEdgetoGraph(4, 7);
    // array to store the nodes present under of subtree
    // of every node in a tree
    int nodesunder[n + 1];
    dfs(nodesunder, 1, 0); // generating our nodesunder array
    mark(); // marking the indices in map
    // Query 1
    printDFS(2, nodesunder);
    // Query 2
    printDFS(4, nodesunder);
    return 0;
}

出力

The DFS of subtree 2: 2 4 6 7 5
The DFS of subtree 4: 4 6 7

コードを理解する

このアプローチでは、dfsの順序を事前計算し、それをベクトルに格納します。dfsを事前計算したら、各ノードから開始して各サブツリーの下に存在するノードも計算し、次にノードの開始インデックスからすべてのノードにトラバースします。サブツリー内に存在するノードの数。

結論

このチュートリアルでは、問題を解決して、ツリー内のサブツリーのDFSのクエリを解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常）についても学びました。

同じプログラムをC、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。