为什么树的dfs不需要vis数组，只需要维护父节点就可以？
整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。
难度为阅读建议，可从 ACM 学习索引 按阶段阅读。
无向图无环的，无环的图总是可以展成树的形式。
然后考虑无向图，顶多有回边指向父节点。不可能有回边指向祖先。更不可能有横向边，因为无环啊。所以只需要考虑指向父节点的回边就可以无需使用Vis。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！
相关推荐
整理日期：2026-09-19
二叉树已经知道先序中序推后序
https://www.acwing.com/problem/content/3601/ 不断找新的先序的根节点，根据位置切割中序，根据中序左右子树大小反切割先序，找到左子树对应的先序中序，然后递归处理 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<stdio.h>#include<vector>#include<map>#include<algorithm>#include <algorithm>#include <iostream>#include<string>using namespace std;#define ll long long//# define int long long#define ull unsigned long long#define pii pair<int,int>#define...
整理日期：2026-09-20
二叉树扩展先序遍历转中序遍历
利用前序遍历的特性，如果左子树不空，下一个一定是左节点，不然就是# 因为是转中序遍历，就在两次遍历之间输出 12345678910111213141516171819202122232425262728#include <iostream>#include <cstring>#include <algorithm>using namespace std;int k;string str;void dfs(){ if (str[k] == '#') { k ++ ; return; } char r = str[k ++ ]; // 根节点 dfs(); // 左子树 cout << r << ' '; dfs(); // 右子树}int main(){ cin >> str; dfs(); return 0;}
整理日期：2026-09-21
二叉树给出先序和中序遍历序列，求和树 要求输出中序遍历序列；
1.就算不知道用vector的初始化，也可以手动赋值创建子数组。 2.不断找到当前序列对应的根节点，计算他的子节点的总和，在这样递归处理过程中，注意要中序输出，所以对于是先遍历完左子树，然后输出答案，然后遍历右子树 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include <bits/stdc++.h>using namespace std;#define ll long long//# define int long long#define ull unsigned long long#define pii pair<int,int>#define baoliu(x, y) cout << fixed << setprecision(y) << x#define endl "\n"#define...
整理日期：2026-09-16
完全二叉树的公共父结点
1.有点后序遍历的思想，就是先把左子树，右子树的结果算出来，然后合并到根节点。 2.合并时四种情况分类讨论. 3.对于遇到要找的点就可以直接返回，不管另一个点在这个点下面还是在别的子树上，都是正确的 123456789101112131415161718192021222324252627282930313233int n, m;int a[N];int query(int root,int x,int y){ //cerr<<root<<endl; if(root>max(x,y))return -1; if(root==x||root==y)return root; int l=query(2*root,x,y); int r=query(2*root+1,x,y); if(l==-1&&r==-1)return -1; if(l!=-1&&r!=-1)return root; if(l!=-1&&r==-1)return...
整理日期：2026-09-17
树的重心
12345678910111213141516171819202122232425262728const int N=100010;int n, a, b;vector<int> e[N];//用vector作邻接表int siz[N], pos, ans=1e9;void dfs(int x, int fa){ siz[x]=1; int mx=0; for(auto y : e[x]){ if(y == fa) continue; dfs(y, x);//先搜完，再统计答案 siz[x] += siz[y]; mx=max(mx, siz[y]); } mx=max(mx, n-siz[x]);//维护了重心是pos if(mx<ans) ans=mx,pos=x;}int main(){ scanf("%d", &n); for(int i=1;i<n;i++){ ...
整理日期：2026-09-18
给出中序和按层遍历，求该树的先序遍历，后序遍历，叶子结点。
一切的核心是怎么利用中序和按层遍历构建二叉树？ 1.优化空间很大，可以提前预处理记录每个数对应的位置，还可以vis数组记录这个点是不是已经作为根了。 2.我们考虑到每次找到当前中序要处理区间，里面的数记为集合mid，我们从前到后看层序遍历中的哪个数最先出现在mid中。那么这个数就是当前中序处理区间的根，这个新根的左边是左子树，右边是右子树，我们可以递归处理。 3.对于叶子节点，就是当他作为根的时候，没有左右节点，也就无法进行进一步深搜，flag记一下就可以了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include<stdio.h>#include<vector>#include<map>#include<algorithm>#include...
最新文章