一、树1、后序中序遍历求层序遍历https://pintia.cn/problem-sets/994805342720868352/exam/problems/type/7?problemSetProblemId994805485033603072#includebits/stdc.h #define ll long long #define endl \n #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const ll N3e510; vectorll in,post,level; ll n; struct Node { ll val; Node *l,*r; Node(ll v):val(v),l(NULL),r(NULL){} }; Node* build(ll il,ll ir,ll pl,ll pr) { if(ilir) return NULL;//空吗没有节点返回必须返回空 ll rootpost[pr]; //根节点 Node* unew Node(root);//创建根节点 ll pil;//下标 while(in[p]!root) { p; } ll cnp-il; //左子树节点数量 u-lbuild(il,p-1,pl,plcn-1); u-rbuild(p1,ir,plcn,pr-1);//pr是根去掉 return u; } void bfs(Node* root) { queueNode* q; q.push(root); while(q.size()) { Node* uq.front(); q.pop(); level.push_back(u-val); if(u-l) q.push(u-l); if(u-r) q.push(u-r); } } void solve() { cinn; for(ll i0;in;i) { ll x; cinx; post.push_back(x); } for(ll i0;in;i) { ll x; cinx; in.push_back(x); } Node* rootbuild(0,n-1,0,n-1); bfs(root); for(ll i0;in;i) { if(i) cout ; coutlevel[i]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll T1; // cinT; while(T--) { solve(); } return 0; }2、前序中序遍历求层序遍历输入先序中序74 1 3 2 6 5 71 2 3 4 5 6 7输出4 1 6 3 5 7 2#includebits/stdc.h #define ll long long #define endl \n #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const ll N3e510; vectorll pre,in,level; ll n; struct Node { ll val; Node *l,*r; Node(ll v): val(v),l(NULL),r(NULL){} }; Node* build(ll il,ll ir,ll pl,ll pr) { if(ilir) return NULL; ll rootpre[pl]; Node* unew Node(root); ll pil; while(in[p]!root) { p; } ll cnp-il; u-lbuild(il,p-1,pl1,plcn); //一段长度为 cnt 的区间 //起点 s终点 s cnt - 1 //因为前序左子树起点是pl1,所以终点是pl1cn-1plcn u-rbuild(p1,ir,plcn1,pr); return u; } void bfs(Node* root) { queueNode* q; q.push(root); while(q.size()) { Node* uq.front(); q.pop(); level.push_back(u-val); if(u-l) q.push(u-l); if(u-r) q.push(u-r); } } void solve() { cinn; for(ll i0;in;i) { ll x; cinx; pre.push_back(x); } for(ll i0;in;i) { ll x; cinx; in.push_back(x); } Node* rootbuild(0,n-1,0,n-1); bfs(root); for(ll i0;in;i) { if(i) cout ; coutlevel[i]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll T1; // cinT; while(T--) { solve(); } return 0; }3、层序中序遍历求后序遍历输入层序中序74 1 6 3 5 7 21 2 3 4 5 6 7输出2 3 1 5 7 6 4#includebits/stdc.h #define ll long long #define endl \n #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const ll N3e510; vectorll in,level,post; ll n; struct Node { ll val; Node *l,*r; Node(ll v):val(v),l(NULL),r(NULL) {} }; Node* build(ll il,ll ir,vectorll lev) { if(ilir) return NULL; // 层序第一个就是根 ll rootlev[0]; Node* unew Node(root); // 在中序里找到根的位置 ll pil; while(in[p]!root) { p; } // 拆分左子树的层序、右子树的层序 vectorll levl,levr; for(ll i1;ilev.size();i) { bool leftfalse; for(ll jil;jp;j) { if(lev[i]in[j]) { lefttrue; break; } } if(left) levl.push_back(lev[i]); else levr.push_back(lev[i]); } u-lbuild(il,p-1,levl); u-rbuild(p1,ir,levr); return u; } void dfs(Node* root) { if(!root) return ; dfs(root-l); dfs(root-r); post.push_back(root-val); } void solve() { cinn; for(ll i0;in;i) { ll x; cinx; level.push_back(x); } for(ll i0;in;i) { ll x; cinx; in.push_back(x); } Node* rootbuild(0,n-1,level); dfs(root); for(ll i0;in;i) { if(i) cout ; coutpost[i]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll T1; // cinT; while(T--) { solve(); } return 0; }4、堆判断 后序遍历https://pintia.cn/problem-sets/994805342720868352/exam/problems/type/7?problemSetProblemId994805342821531648page1#includebits/stdc.h #define ll long long #define endl \n using namespace std; const ll N3e510; ll n,m; ll v[N]; bool Max(ll x) { if(2*xn) { if(v[2*x] v[x]) return false; if(!Max(2*x)) return false; } if(2*x1n) { if(v[2*x1] v[x]) return false; if(!Max(2*x1)) return false; } return true; } bool Min(ll x) { if(2*xn) { if(v[2*x] v[x]) return false; if(!Min(2*x)) return false; } if(2*x1n) { if(v[2*x1] v[x]) return false; if(!Min(2*x1)) return false; } return true; } void post(ll x) { if(xn) return ; post(2*x); post(2*x1); coutv[x]; if(x!1) cout ; } void solve() { for(ll i1;in;i) cinv[i]; if(Max(1)) cout Max Heap\n; else if(Min(1)) cout Min Heap\n; else cout Not Heap\n; post(1); coutendl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll T; cinmn; while(m--) solve(); return 0; }5、L3-010 是否完全二叉搜索树https://pintia.cn/problem-sets/2031695228828352512/exam/problems/type/7?page1problemSetProblemId2031695229042262069#includebits/stdc.h #define ll long long #define endl \n #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const ll N3e510; ll n; vectorll level; struct Node { ll val; Node *l,*r; Node(ll v): val(v),l(NULL),r(NULL){} }; Node* build(Node* root,ll x) { if(!root) return new Node(x); if(xroot-val) root-lbuild(root-l,x); if(xroot-val) root-rbuild(root-r,x); return root; } bool bfs(Node* root) { queueNode* q; q.push(root); bool ffalse; bool oktrue; while(q.size()) { Node* uq.front(); q.pop(); if(uNULL) { ftrue; continue; } level.push_back(u-val);//因为后面没有判空所以需要先判空才能加入val if(f) okfalse; q.push(u-l);//跟之前不一样不用判空直接加入,详细见下 q.push(u-r); } return ok; } void solve() { cinn; Node* rootNULL; for(ll i0;in;i) { ll x; cinx; rootbuild(root,x); } bool fbfs(root); for(ll i0;in;i) { if(i) cout ; coutlevel[i]; } coutendl; if(f) coutYES; else coutNO; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll T1; while(T--) { solve(); } return 0; }所以必须把 45 的左节点空和 24 的左节点空加入为的是判断是不是完全二叉树。6、L3-016 二叉搜索树的结构https://pintia.cn/problem-sets/2031695228828352512/exam/problems/type/7?page1problemSetProblemId2031695229042262075#includebits/stdc.h #define ll long long #define endl \n #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const ll N3e510; struct Node { ll val; Node *l,*r; Node(ll v):val(v),l(NULL),r(NULL){} }; mapll,ll lev; mapll,Node*fa; Node* build(Node* root,ll x,ll cn,Node* faa) { if(!root) { rootnew Node(x); lev[x]cn; fa[x]faa; return root; } if(xroot-val) root-lbuild(root-l,x,cn1,root); if(xroot-val) root-rbuild(root-r,x,cn1,root); return root; } void solve() { ll n; cinn; Node* rootNULL; for(ll i0;in;i) { ll x; cinx; rootbuild(root,x,1,NULL); } ll m; cinm; cin.get(); while(m--) { ll x,y; string s; cinxs; if(s[0]i) { cinss; if(s[1]o) { if(xroot-val) coutYesendl; else coutNoendl; } else if(s[0]p) { cinsy; if(fa.count(y)fa[y]fa[y]-valx) coutYesendl; else coutNoendl; } else if(s[0]l) { cinssy; if(fa.count(x)fa[x]fa[x]-lfa[x]-valyfa[x]-l-valx) coutYesendl; else coutNoendl; } else if(s[0]r) { cinssy; if(fa.count(x)fa[x]fa[x]-rfa[x]-valyfa[x]-r-valx) coutYesendl; else coutNoendl; } } else if(s[0]a) { cinyss; if(s[0]s) { if(fa.count(x)fa.count(y)fa[x]fa[y]fa[x]-valfa[y]-val) coutYesendl; else coutNoendl; } else if(s[0]o) { cinsss; if(lev.count(x)lev.count(y)lev[x]lev[y]) coutYesendl; else coutNoendl; } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll T1; while(T--) { solve(); } return 0; }7、7-147 完全二叉树的层序遍历https://pintia.cn/problem-sets/2031695228828352512/exam/problems/type/7?page1problemSetProblemId2031695229042262095#includebits/stdc.h #define ll long long #define endl \n #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const ll N3e510; ll tree[34],a[34]; ll n,cn1; void build(ll idx) { if(idxn) return; tree[idx]a[cn]; build(2*idx1); build(2*idx); } void solve() { cinn; for(ll in;i1;i--) { cina[i]; } build(1); for(ll i1;in;i) { if(i!1) cout ; couttree[i]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll T1; while(T--) { solve(); } return 0; }二、图1、dijkstra堆优化模板(代码随想录)https://www.programmercarl.com/kamacoder/0047.%E5%8F%82%E4%BC%9Adijkstra%E5%A0%86.html#%E6%80%9D%E8%B7%AF#include iostream #include vector #include list #include queue #include climits using namespace std; // 小顶堆 class mycomparison { public: bool operator()(const pairint, int lhs, const pairint, int rhs) { return lhs.second rhs.second; } }; // 定义一个结构体来表示带权重的边 struct Edge { int to; // 邻接顶点 int val; // 边的权重 Edge(int t, int w): to(t), val(w) {} // 构造函数 }; int main() { int n, m, p1, p2, val; cin n m; vectorlistEdge grid(n 1); for(int i 0; i m; i){ cin p1 p2 val; // p1 指向 p2权值为 val grid[p1].push_back(Edge(p2, val)); } int start 1; // 起点 int end n; // 终点 // 存储从源点到每个节点的最短距离 std::vectorint minDist(n 1, INT_MAX); // 记录顶点是否被访问过 std::vectorbool visited(n 1, false); // 优先队列中存放 pair节点源点到该节点的权值 priority_queuepairint, int, vectorpairint, int, mycomparison pq; // 初始化队列源点到源点的距离为0所以初始为0 pq.push(pairint, int(start, 0)); minDist[start] 0; // 起始点到自身的距离为0 while (!pq.empty()) { // 1. 第一步选源点到哪个节点近且该节点未被访问过 通过优先级队列来实现 // 节点 源点到该节点的距离 pairint, int cur pq.top(); pq.pop(); if (visited[cur.first]) continue; // 2. 第二步该最近节点被标记访问过 visited[cur.first] true; // 3. 第三步更新非访问节点到源点的距离即更新minDist数组 for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点cur指向的节点为 edge // cur指向的节点edge.to这条边的权值为 edge.val if (!visited[edge.to] minDist[cur.first] edge.val minDist[edge.to]) { // 更新minDist minDist[edge.to] minDist[cur.first] edge.val; pq.push(pairint, int(edge.to, minDist[edge.to])); } } } if (minDist[end] INT_MAX) cout -1 endl; // 不能到达终点 else cout minDist[end] endl; // 到达终点最短路径 }7-209 人生就像一场旅行双关键字dij)https://pintia.cn/problem-sets/2031695228828352512/exam/problems/type/7?page2problemSetProblemId2031695229046456322#includebits/stdc.h #define ll long long #define endl \n #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const ll N510; typedef pairll,ll pii; typedef pairll,pii pii2; vectorvectorpii2 g(N1); void solve() { ll b,n,m,k; cinbnmk; for(ll i0;im;i) { ll u,v,val,mood; cinuvvalmood; g[u].push_back({v,{val,mood}}); g[v].push_back({u,{val,mood}}); } while(k--) { ll x; cinx; ll prib; vectorll dist(n1,inf),md(N1,0); vectorbool vis(n1,false); priority_queuepii,vectorpii,greaterpiipq; dist[x]0; pq.push({0,x}); while(pq.size()) { auto itpq.top(); ll dit.first; ll uit.second; pq.pop(); if(vis[u]) continue; vis[u]true; if(dist[u]inf) continue; for(auto it2:g[u]) { ll vit2.first; ll wit2.second.first; ll moit2.second.second; if(dist[v]dist[u]w) { dist[v]dist[u]w; md[v]md[u]mo; pq.push({dist[v],v}); } else if(dist[v]dist[u]wmd[v]md[u]mo) { md[v]md[u]mo; } } } vectorll ans; for(ll i1;in;i) { if(i!xdist[i]b) ans.push_back(i); } if(ans.empty()) { coutT_Tendl; continue; } for(ll i0;ians.size();i) { if(i) cout ; coutans[i]; } coutendl; ll Max-1; for(ll x:ans) { Maxmax(Max,md[x]); } vectorll M; for(ll x:ans) { if(md[x]Max) M.push_back(x); } for(ll i0;iM.size();i) { if(i) cout ; coutM[i]; } coutendl; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll T1; while(T--) { solve(); } return 0; }