題目來源：團體程序設(shè)計天梯賽-練習(xí)集
題目地址：L2-006 樹的遍歷

題目大意

給定一棵二叉樹的后序遍歷和中序遍歷，請你輸出其層序遍歷的序列。這里假設(shè)鍵值都是互不相等的正整數(shù)。

預(yù)備知識：
中序遍歷（Inorder Traversal）：先遍歷左子樹，再訪問更節(jié)點，最后遍歷右子樹。
后續(xù)遍歷（Postorder Traversal）：先遍歷左子樹，再遍歷右子樹，最后訪問根節(jié)點。
（注意：遍歷子樹的時候也要按照相應(yīng)的的方式遍歷。）

我們可以通過一顆二叉樹的前序遍歷和中序遍歷或者后序遍歷和中序遍歷來確定一顆二叉樹。

題目分析

我們可以根據(jù)它給出的后序遍歷和中序遍歷，進行二叉樹的建樹，然后用bfs求出該二叉樹的層序遍歷，最后輸出就可以了。

下面就簡單講一下，怎么通過后序遍歷和中序遍歷的結(jié)果來得出二叉樹的結(jié)構(gòu)。

設(shè)中序遍歷序列為 $in\_ordered$ ，其范圍為 $[la,ra]$；后序遍歷序列為 $post\_ordered$ ，其范圍為 $[lb,rb]$。

• 根據(jù)后續(xù)遍歷的性質(zhì)，可以知道 $post\_ordered[rb]$ 為根節(jié)點。然后我們在中序遍歷序列 $in\_ordered$ 中找出根節(jié)點的位置。
• 至此，我們已經(jīng)可以知道 $in\_ordered$ 中，左右子樹的范圍分為別為 $[la,p?1]$ 和 $[p+1,ra]$。于是，我們就可以求出左子樹的節(jié)點個數(shù)：
  $$cnt=p?la$$
• 接著，我們就可以求出后序遍歷 $post\_ordered$ 中左右子樹的范圍了。有了以上信息，我們就可以利用同樣的方法對求左子樹的相關(guān)信息，進行遞歸建樹，進而得到整棵二叉樹的結(jié)構(gòu)。

（上述過程的圖示）

有了二叉樹結(jié)構(gòu)，層序遍歷還不好求？其實沒什么好說的，就是一個很普通的bfs，這里就不展開了。

坑點：

• 題目沒有給出樹節(jié)點鍵值的范圍，如果鍵值很大，那么用鍵值作為數(shù)組下標存儲左右節(jié)點位置的方法會導(dǎo)致數(shù)組越界，還好本題良心，放了我一馬。
• 題目有明說，注意輸出格式，看題要認真。

其實這種題目很沒營養(yǎng)的，都是同一個套路。你第一次遇到會覺得學(xué)到東西了，覺得很開心。第二次遇到就是秒切了，第三次就會厭倦，第四次……

代碼如下

#include <bits/stdc++.h>using namespace std; const int maxn = 50; int n; /*** in_order[]表示中序遍歷序列* post_order[]表示后序遍歷序列* tree[]用于存儲樹形結(jié)構(gòu)* 其中，tree[i].first表示i節(jié)點左孩子編號，tree[i].second表示i號節(jié)點右孩子編號*/ int in_order[maxn], post_order[maxn]; pair<int, int> tree[maxn]; /*** [la, ra]表示中序遍歷序列的范圍* [lb, rb]表示后序遍歷序列的范圍*/ int build(int la, int ra, int lb, int rb) {if (la > ra || lb > rb) return 0;int rt = post_order[rb];//p表示根節(jié)點在中序遍歷序列中的位置int p = la;while (in_order[p] != rt) p++;//cnt表示左子樹的節(jié)點數(shù)int cnt = p - la;//根據(jù)已知量，求左右子樹所在的遍歷序列區(qū)間tree[rt].first = build(la, p - 1 , lb, lb + cnt - 1);tree[rt].second = build(p + 1, ra, lb + cnt, rb - 1);return rt; }/*** 利用bfs層序遍歷二叉樹* @param root表示二叉樹的根節(jié)點*/ void bfs(int root) {vector<int> ans;queue<int> q;q.push(root);while (!q.empty()) {int node = q.front();q.pop();ans.push_back(node);if (tree[node].first) q.push(tree[node].first);if (tree[node].second) q.push(tree[node].second);}int len = ans.size();for (int i = 0; i < len; i++)cout << ans[i] << (i == len - 1 ? '\n' : ' '); }int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> post_order[i];for (int i = 1; i <= n; i++)cin >> in_order[i];int root = build(1, n, 1, n);bfs(root);return 0; }

---

如果本文對你有所幫助，要記得點贊哦~

總結(jié)

以上是生活随笔為你收集整理的L2-006 树的遍历-团体程序设计天梯赛GPLT的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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