L2-006. 樹的遍歷

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

輸入格式：

輸入第一行給出一個(gè)正整數(shù)N（<=30），是二叉樹中結(jié)點(diǎn)的個(gè)數(shù)。第二行給出其后序遍歷序列。第三行給出其中序遍歷序列。數(shù)字間以空格分隔。

輸出格式：

在一行中輸出該樹的層序遍歷的序列。數(shù)字間以1個(gè)空格分隔，行首尾不得有多余空格。

輸入樣例： 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 輸出樣例： 4 1 6 3 5 7 2

思路：偷個(gè)懶不創(chuàng)建二叉樹的，直接遞歸知道每個(gè)數(shù)是第幾層然后存放在優(yōu)先隊(duì)列中，但是沒有AC，然后我想了一下好像一層中的鍵值出現(xiàn)的順序可能不一樣，開始覺得這種方法是錯(cuò)誤的，但是后面想了一下，根據(jù)中序能知道同一層元素中輸出的優(yōu)先順序，于是加入了在結(jié)構(gòu)體中quan，這個(gè)就是最后一個(gè)測(cè)試點(diǎn)。
#include<set> #include<map> #include<queue> #include<iostream> #include<algorithm> using namespace std; struct Node{int key;int quan;int ceng;bool operator < (const Node &a)const{if (a.ceng!=ceng)return a.ceng < ceng;else return a.quan < quan;} }; int n; int b[40]; map<int, int>ma; priority_queue<Node>que; void Print(int s,int e,int c) {if (s>e)return;Node node;if (s == e){node.ceng = c;node.quan = s;node.key = b[s];que.push(node);}else{int max = ma[b[s]], ss = s;for (int i = s; i <= e; i++)if (ma[b[i]] > max){max = ma[b[i]];ss = i;}node.ceng = c;node.quan = ss;node.key = b[ss];que.push(node);Print(s, ss - 1, c + 1);Print(ss + 1, e, c + 1);}} int main() {cin >> n;for (int i = 0; i < n; i++){int num; cin >> num;ma.insert(pair<int, int>(num, i));}for (int i = 0; i < n; i++)cin >> b[i];Print(0, n - 1, 0);for (int i = 1; i <= n; i++){if (i == 1)cout << que.top().key;else cout << " " << que.top().key;que.pop();}cout << endl;return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/zengguoqiang/p/8652361.html

總結(jié)

以上是生活随笔為你收集整理的L2-006. 树的遍历（不建树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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