第二周 题目练习4（二叉树的遍历+二叉树深度+二叉树宽度+二叉树共同祖先LCA）洛谷P4913 B3642 P1305 P3884

P4913 【深基16.例3】二叉树深度 - 洛谷解题过程二叉树求深度模板 不同于课本上的直接递归//直接递归 ll depth(BiTree T) { if(TNULL) { return 0; } mdepth(T-lchild); ndepth(T-rchild); if(mn) { return (m1); } else { return (n1); } }//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; }sizeq.size()可以保证内层循环for可以将这一层处理好 每层处理好之后 再depth可以保证不溢出//BFS层次遍历 queuellq; q.push(1); ll depth0; while(!q.empty()) { depth; ll sizeq.size(); for(ll i0;isize;i) { ll tq.front(); q.pop(); if(l[t]!0)q.push(l[t]); if(r[t]!0)q.push(r[t]); } }稍微改动一下就可以求widthll depth0; ll width0; while(!q.empty()) { depth; ll sizeq.size(); widthmax(width,size); //更新最大宽度 for(ll i0;isize;i) { ll tq.front(); q.pop(); if(l[t]!0)q.push(l[t]); if(r[t]!0)q.push(r[t]); } } coutdepth widthendl;实现代码#includebits/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 coutYESendl; #define NO coutNOendl; #define MAXSIZE 1000005 using namespace std; ll n; ll l[MAXSIZE]; ll r[MAXSIZE]; int main() { IOS cinn; for(ll i1;in;i) { cinl[i]r[i]; } queuellq; q.push(1); ll depth0; while(!q.empty()) { depth; ll sizeq.size(); for(ll i0;isize;i) { ll tq.front(); q.pop(); if(l[t]!0)q.push(l[t]); if(r[t]!0)q.push(r[t]); } } coutdepthendl; // coutfixedsetprecision(x) ; return 0; }B3642 二叉树的遍历 - 洛谷解题过程先序第一次碰到节点就输出弹出t– cout t然后压孩子不需要回头不需要标记。中序靠不断往左走的循环控制时机依靠指针t一路向左天然等到左子树走完再输出不用标记。后序弹出节点的时候你无法判断左右子树有没有遍历完毕不加标记分不清状态所以必须打上标签实现代码#includebits/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 coutYESendl; #define NO coutNOendl; #define MAXSIZE 1000005 using namespace std; ll n; ll l[MAXSIZE]; ll r[MAXSIZE]; void one() { stackllst; st.push(1); //先序 根左右 while(!st.empty()) { ll tst.top(); st.pop(); coutt ; if(r[t]!0)st.push(r[t]); if(l[t]!0)st.push(l[t]); } } //中序 左根右 void two() { stackllst; ll t1; while(t||!st.empty()) { while(t) { st.push(t); tl[t]; } tst.top(); st.pop(); coutt ; tr[t]; } } void three() { stackpairll,boolst; st.push({1,false}); while(!st.empty()) { pairll,boolcurst.top(); ll tcur.fi; bool viscur.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 { coutt ; } } } int main() { IOS cinn; for(ll i1;in;i) { cinl[i]r[i]; } one(); coutendl; two(); coutendl; three(); coutendl; // coutfixedsetprecision(x) ; return 0; }P1305 新二叉树 - 洛谷这个题跟上个题一样 唯一的不一样就是他的根是输入的 刚开始忘记这个了实现代码#includebits/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 coutYESendl; #define NO coutNOendl; #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) { stackcharst; st.push(root); //先序 根左右 while(!st.empty()) { char tst.top(); st.pop(); coutt; if(r[t]!*)st.push(r[t]); if(l[t]!*)st.push(l[t]); } } int main() { IOS cinn; char root; for(ll i0;in;i) { cinidl1r1; if(i0) { rootid; } l[id]l1; r[id]r1; } one(root); // coutfixedsetprecision(x) ; return 0; }[P3884JLOI2009] 二叉树问题 - 洛谷解题过程说明 LCA最近公共祖先深度最大求深度DFS(递归LCA) 无向树优点可以直接储存depthwidthfa[u];void dfs(int u,int father) { // 记录当前节点u的直接父亲 fa[u]father; // 当前节点层数 父节点层数 1 dep[u]dep[father]1; // 当前所在层的节点数量1用来后续求宽度 layer[dep[u]]; //持续更新全局最大层数遍历结束maxdepth就是树的深度答案 maxdepthmax(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() { queuellq; 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 width0; for(ll i1;imaxdepth;i) { widthmax(width,layer[i]); }求距离 [共同祖先LCA] 设ans是共同祖先dx为x到ans的边数 dy是y到ans的边数距离dis2*dxdy//暴力LCA一步一步找 ll findLCA(ll x,ll y) { unordered_setlls; while(x!0)//收集 x 的全部祖先 { s.insert(x); xfa[x]; } while(!s.count(y))//y 向上找第一个重合祖先 { yfa[y]; } return y; }//倍增LCA 一次跳多步 //LOG 是我们自定义的常数代表倍增最大层数 //预处理倍增数组 void pre() { for(int k1;kLOG;k) { for(int u1;un;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 kLOG-1;k0;k--) { if(dep[x] - (1k) dep[y]) { x fa[k][x]; } } if(x y) return x; //第二步同步向上跳 for(int kLOG-1;k0;k--) { if(fa[k][x] ! fa[k][y]) { xfa[k][x]; yfa[k][y]; } } return fa[0][x]; }代码实现//暴力LCA #includebits/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 coutYESendl; #define NO coutNOendl; #define MAXSIZE 105 using namespace std; vectorllg[MAXSIZE];//邻接表存树的边 ll dep[MAXSIZE]; //dep[u]节点u所在层数深度 ll fa[MAXSIZE];//fa[u]节点u的直接父节点 ll layer[MAXSIZE]; //layer[k]第k层一共有多少个节点 ll maxdepth0; ll n; void dfs(ll u,ll father) { fa[u]father; dep[u]dep[father]1; layer[dep[u]]; maxdepthmax(maxdepth,dep[u]); for(ll v:g[u]) { if(v!father) { dfs(v,u); } } } ll findLCA(ll x,ll y) { unordered_setlls; while(x!0) { s.insert(x); xfa[x]; } while(!s.count(y)) { yfa[y]; } return y; } int main() { IOS cinn; for(ll i1;in;i) { ll u,v; cinuv; g[u].push_back(v); g[v].push_back(u); } ll x,y; cinxy; //求深度 dep[0]0; dfs(1,0); //求宽度 ll width0; for(ll i1;imaxdepth;i) { widthmax(width,layer[i]); } //计算祖先 ll afindLCA(x,y); ll dxdep[x]-dep[a]; ll dydep[y]-dep[a]; ll ans2*dxdy; coutmaxdepthendl; coutwidthendl; coutansendl; // coutfixedsetprecision(x) ; return 0; }//倍增LCA #includebits/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; vectorllg[MAXSIZE]; ll dep[MAXSIZE]; ll fa[LOG][MAXSIZE]; //倍增表 fa[k][u] ll layer[MAXSIZE]; ll maxdepth0; ll n; //DFS 预处理dep 和 fa[0]父亲结点 void dfs(ll u,ll father) { fa[0][u]father; dep[u]dep[father]1; layer[dep[u]]; maxdepthmax(maxdepth,dep[u]); for(ll v:g[u]) { if(v!father) { dfs(v,u); } } } //预处理倍增数组 void pre() { for(int k1;kLOG;k) { for(int u1;un;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 kLOG-1;k0;k--) { if(dep[x] - (1k) dep[y]) { x fa[k][x]; } } if(x y) return x; //第二步同步向上跳 for(int kLOG-1;k0;k--) { if(fa[k][x] ! fa[k][y]) { xfa[k][x]; yfa[k][y]; } } return fa[0][x]; } int main() { IOS cinn; for(ll i1;in;i) { ll u,v; cinuv; g[u].push_back(v); g[v].push_back(u); } ll x,y; cinxy; dep[0]0; dfs(1,0); pre(); //构建倍增表 //求宽度 ll width0; for(ll i1;imaxdepth;i) { widthmax(width,layer[i]); } ll ancestor LCA(x,y); ll dxdep[x]-dep[ancestor]; ll dydep[y]-dep[ancestor]; ll ans2*dxdy; coutmaxdepthendl; coutwidthendl; coutansendl; return 0; }