第二周 题目练习4（二叉树的遍历+二叉树深度+二叉树宽度+二叉树共同祖先LCA）洛谷P4913 B3642 P1305 P3884
P4913 【深基16.例3】二叉树深度 - 洛谷
解题过程
二叉树求深度模板 不同于课本上的直接递归
//直接递归 ll depth(BiTree T) { if(T==NULL) { return 0; } m=depth(T->lchild); n=depth(T->rchild); if(m>n) { return (m+1); } else { return (n+1); } }//DFS递归 ll dfs(ll u) { if(u == 0) return 0; ll ld = dfs(l[u]); ll rd = dfs(r[u]); return max(ld, rd) + 1; }size=q.size()可以保证内层循环for可以将这一层处理好 每层处理好之后 再depth++
可以保证不溢出
//BFS层次遍历 queue<ll>q; q.push(1); ll depth=0; while(!q.empty()) { depth++; ll size=q.size(); for(ll i=0;i<size;i++) { ll t=q.front(); q.pop(); if(l[t]!=0)q.push(l[t]); if(r[t]!=0)q.push(r[t]); } }稍微改动一下就可以求width
ll depth=0; ll width=0; while(!q.empty()) { depth++; ll size=q.size(); width=max(width,size); //更新最大宽度 for(ll i=0;i<size;i++) { ll t=q.front(); q.pop(); if(l[t]!=0)q.push(l[t]); if(r[t]!=0)q.push(r[t]); } } cout<<depth<<" "<<width<<endl;实现代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES cout<<"YES"<<endl; #define NO cout<<"NO"<<endl; #define MAXSIZE 1000005 using namespace std; ll n; ll l[MAXSIZE]; ll r[MAXSIZE]; int main() { IOS cin>>n; for(ll i=1;i<=n;i++) { cin>>l[i]>>r[i]; } queue<ll>q; q.push(1); ll depth=0; while(!q.empty()) { depth++; ll size=q.size(); for(ll i=0;i<size;i++) { ll t=q.front(); q.pop(); if(l[t]!=0)q.push(l[t]); if(r[t]!=0)q.push(r[t]); } } cout<<depth<<endl; // cout<<fixed<<setprecision(x)<< ; return 0; }B3642 二叉树的遍历 - 洛谷
解题过程
先序：
第一次碰到节点就输出
弹出t–> cout << t
然后压孩子
不需要回头，不需要标记。
中序：
靠不断往左走的循环控制时机
依靠指针t一路向左，天然等到左子树走完再输出，不用标记。
后序：
弹出节点的时候，你无法判断：
左右子树有没有遍历完毕？
不加标记，分不清状态，所以必须打上标签
实现代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES cout<<"YES"<<endl; #define NO cout<<"NO"<<endl; #define MAXSIZE 1000005 using namespace std; ll n; ll l[MAXSIZE]; ll r[MAXSIZE]; void one() { stack<ll>st; st.push(1); //先序 根左右 while(!st.empty()) { ll t=st.top(); st.pop(); cout<<t<<" "; if(r[t]!=0)st.push(r[t]); if(l[t]!=0)st.push(l[t]); } } //中序 左根右 void two() { stack<ll>st; ll t=1; while(t||!st.empty()) { while(t) { st.push(t); t=l[t]; } t=st.top(); st.pop(); cout<<t<<" "; t=r[t]; } } void three() { stack<pair<ll,bool>>st; st.push({1,false}); while(!st.empty()) { pair<ll,bool>cur=st.top(); ll t=cur.fi; bool vis=cur.se; st.pop(); if(!vis) { st.push({t,true}); if(r[t]) st.push({r[t],false}); if(l[t]) st.push({l[t],false}); } else { cout<<t<<" "; } } } int main() { IOS cin>>n; for(ll i=1;i<=n;i++) { cin>>l[i]>>r[i]; } one(); cout<<endl; two(); cout<<endl; three(); cout<<endl; // cout<<fixed<<setprecision(x)<< ; return 0; }P1305 新二叉树 - 洛谷
这个题跟上个题一样 唯一的不一样就是他的根是输入的 刚开始忘记这个了
实现代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES cout<<"YES"<<endl; #define NO cout<<"NO"<<endl; #define MAXSIZE 256 using namespace std; ll n; char l[MAXSIZE]; char r[MAXSIZE]; char c[MAXSIZE]; char id,l1,r1; void one(char root) { stack<char>st; st.push(root); //先序 根左右 while(!st.empty()) { char t=st.top(); st.pop(); cout<<t; if(r[t]!='*')st.push(r[t]); if(l[t]!='*')st.push(l[t]); } } int main() { IOS cin>>n; char root; for(ll i=0;i<n;i++) { cin>>id>>l1>>r1; if(i==0) { root=id; } l[id]=l1; r[id]=r1; } one(root); // cout<<fixed<<setprecision(x)<< ; return 0; }[P3884JLOI2009] 二叉树问题 - 洛谷
解题过程
说明： LCA：最近公共祖先（深度最大）
求深度：
DFS(递归+LCA) 无向树
优点：可以直接储存depth，width，fa[u];
void dfs(int u,int father) { // 记录当前节点u的直接父亲 fa[u]=father; // 当前节点层数 = 父节点层数 +1 dep[u]=dep[father]+1; // 当前所在层的节点数量+1，用来后续求宽度 layer[dep[u]]++; //持续更新全局最大层数，遍历结束maxdepth就是树的深度答案 maxdepth=max(maxdepth,dep[u]); // 遍历和u相连的所有节点（邻接表无向存储，正反都存了边） for(int v:g[u]) { // 关键v是父节点就跳过，避免往回走死循环 if(v != father) { dfs(v,u);// v是u的子节点递归u变成v的父节点 } } }BFS(单独涉及二叉树深度使用)
// BFS层序遍历，替代DFS void bfs() { queue<ll>q; q.push(1); fa[0][1] = 0; //根节点1的父亲是0 dep[1] = 1; layer[1]++; maxdepth = 1; while(!q.empty()) { ll u = q.front(); q.pop(); for(ll v : g[u]) { if(v != fa[0][u]) //不回走父节点 { fa[0][v] = u; dep[v] = dep[u] + 1; layer[dep[v]]++; maxdepth = max(maxdepth, dep[v]); q.push(v); } } } }求宽度：
ll width=0; for(ll i=1;i<=maxdepth;i++) { width=max(width,layer[i]); }求距离 [共同祖先（LCA）] ：
设ans是共同祖先
dx为：x到ans的边数 dy是y到ans的边数
距离dis=2*dx+dy
//暴力LCA一步一步找 ll findLCA(ll x,ll y) { unordered_set<ll>s; while(x!=0)//收集 x 的全部祖先 { s.insert(x); x=fa[x]; } while(!s.count(y))//y 向上找第一个重合祖先 { y=fa[y]; } return y; }//倍增LCA 一次跳多步 //LOG 是我们自定义的常数，代表倍增最大层数 //预处理倍增数组 void pre() { for(int k=1;k<LOG;k++) { for(int u=1;u<=n;u++) { fa[k][u] = fa[k-1][ fa[k-1][u] ]; } } } ll LCA(ll x,ll y) { //保证x深度 >= y深度 if(dep[x] < dep[y]) swap(x,y); //第一步：x向上跳到和y同一深度 for(int k=LOG-1;k>=0;k--) { if(dep[x] - (1<<k) >= dep[y]) { x = fa[k][x]; } } if(x == y) return x; //第二步：同步向上跳 for(int k=LOG-1;k>=0;k--) { if(fa[k][x] != fa[k][y]) { x=fa[k][x]; y=fa[k][y]; } } return fa[0][x]; }代码实现
//暴力LCA #include<bits/stdc++.h> #define ll long long #define endl '\n' #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES cout<<"YES"<<endl; #define NO cout<<"NO"<<endl; #define MAXSIZE 105 using namespace std; vector<ll>g[MAXSIZE];//邻接表存树的边 ll dep[MAXSIZE]; //dep[u]：节点u所在层数（深度） ll fa[MAXSIZE];//fa[u]：节点u的直接父节点 ll layer[MAXSIZE]; //layer[k]：第k层一共有多少个节点 ll maxdepth=0; ll n; void dfs(ll u,ll father) { fa[u]=father; dep[u]=dep[father]+1; layer[dep[u]]++; maxdepth=max(maxdepth,dep[u]); for(ll v:g[u]) { if(v!=father) { dfs(v,u); } } } ll findLCA(ll x,ll y) { unordered_set<ll>s; while(x!=0) { s.insert(x); x=fa[x]; } while(!s.count(y)) { y=fa[y]; } return y; } int main() { IOS cin>>n; for(ll i=1;i<n;i++) { ll u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } ll x,y; cin>>x>>y; //求深度 dep[0]=0; dfs(1,0); //求宽度 ll width=0; for(ll i=1;i<=maxdepth;i++) { width=max(width,layer[i]); } //计算祖先 ll a=findLCA(x,y); ll dx=dep[x]-dep[a]; ll dy=dep[y]-dep[a]; ll ans=2*dx+dy; cout<<maxdepth<<endl; cout<<width<<endl; cout<<ans<<endl; // cout<<fixed<<setprecision(x)<< ; return 0; }//倍增LCA #include<bits/stdc++.h> #define ll long long #define endl '\n' #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define MAXSIZE 105 #define LOG 20 //最大2^19步，足够 using namespace std; vector<ll>g[MAXSIZE]; ll dep[MAXSIZE]; ll fa[LOG][MAXSIZE]; //倍增表 fa[k][u] ll layer[MAXSIZE]; ll maxdepth=0; ll n; //DFS 预处理dep 和 fa[0]（父亲结点） void dfs(ll u,ll father) { fa[0][u]=father; dep[u]=dep[father]+1; layer[dep[u]]++; maxdepth=max(maxdepth,dep[u]); for(ll v:g[u]) { if(v!=father) { dfs(v,u); } } } //预处理倍增数组 void pre() { for(int k=1;k<LOG;k++) { for(int u=1;u<=n;u++) { fa[k][u] = fa[k-1][ fa[k-1][u] ]; } } } //倍增查询LCA ll LCA(ll x,ll y) { //保证x深度 >= y深度 if(dep[x] < dep[y]) swap(x,y); //第一步：x向上跳到和y同一深度 for(int k=LOG-1;k>=0;k--) { if(dep[x] - (1<<k) >= dep[y]) { x = fa[k][x]; } } if(x == y) return x; //第二步：同步向上跳 for(int k=LOG-1;k>=0;k--) { if(fa[k][x] != fa[k][y]) { x=fa[k][x]; y=fa[k][y]; } } return fa[0][x]; } int main() { IOS cin>>n; for(ll i=1;i<n;i++) { ll u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } ll x,y; cin>>x>>y; dep[0]=0; dfs(1,0); pre(); //构建倍增表 //求宽度 ll width=0; for(ll i=1;i<=maxdepth;i++) { width=max(width,layer[i]); } ll ancestor = LCA(x,y); ll dx=dep[x]-dep[ancestor]; ll dy=dep[y]-dep[ancestor]; ll ans=2*dx+dy; cout<<maxdepth<<endl; cout<<width<<endl; cout<<ans<<endl; return 0; }