
在这个问题中,我们得到一棵二叉树,我们需要从特定节点执行 dfs,其中我们假设给定节点作为根并从中执行 dfs。

在上面的树中假设我们需要执行 DFS节点 F
在本教程中,我们将应用一些非正统的方法,以便大大降低我们的时间复杂度,因此我们也能够在更高的约束条件下运行此代码。
方法 - 在这种方法中,我们不会简单地采用天真的方法,即我们简单地对每个节点应用 dfs,因为它不适用于更高的约束,因此我们尝试使用一些非正统的方法来避免获得 TLE。
#include <bits>
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 <h2>输出</h2>
<pre class="brush:php;toolbar:false;">The DFS of subtree 2: 2 4 6 7 5
The DFS of subtree 4: 4 6 7
理解代码
在这种方法中,我们预先计算 dfs 的顺序并将其存储在向量中,当我们预先计算 dfs 时,我们还计算从每个节点开始的每个子树下存在的节点,并且然后我们只需从 then 节点的起始索引遍历到其子树中存在的所有节点数。
结论
在本教程中,我们解决了一个问题来解决以下查询:树中子树的 DFS。我们还学习了针对此问题的C++程序以及解决此问题的完整方法(Normal)。
我们可以用其他语言(例如C、java、python等语言)编写相同的程序。希望这篇文章对您有所帮助。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











