https://pintia.cn/problem-sets/994805342720868352/problems/994805380754817024
首先要知道的是:

• 入棧順序就是樹的前序遍歷的順序
• 出棧順序就是樹的中序遍歷的順序

故問題，就轉(zhuǎn)換成了根據(jù)前序遍歷，中序遍歷的順序建樹的過程。
最后遍歷樹輸出后序遍歷的結(jié)果即可。

#include<bits/stdc++.h> using namespace std; vector<int>a,b,ans; stack<int>st; int n; unordered_map<int,int>L,R,S; int build(int l1,int r1,int l2,int r2) {auto root=a[l1];int k=S[root];//找到中序遍歷所對應(yīng)的位置。if(k>l2) L[root]=build(l1+1,l1+k-l2,l2,k-1);if(k<r2) R[root]=build(l1+k-l2+1,r1,k+1,r2);return root; } void dfs(int root) {if(L.count(root)) dfs(L[root]);//有左兒子if(R.count(root)) dfs(R[root]);//有右兒子ans.push_back(root); } int main(void) {cin>>n;for(int i=0;i<n*2;i++){string op; cin>>op;if(op=="Push"){int x; cin>>x;a.push_back(x);st.push(x);}else{int u=st.top(); st.pop();b.push_back(u);}}for(int i=0;i<b.size();i++) S[b[i]]=i;build(0,n-1,0,n-1);//建樹dfs(a[0]);//遍歷樹for(int i=0;i<ans.size();i++) {if(i) cout<<" ";cout<<ans[i];}return 0; }

總結(jié)

以上是生活随笔為你收集整理的1086 Tree Traversals Again (25 分)【一般 / 建树 树的遍历】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。