#include<bits/stdc++.h>
using namespace std;
int main(){
struct Node {
int val,l,r;
} node[MAX];
int tot;
int c[MAX],b[MAX];
int dfs(int len,int b[],int c[]) {//中序剪芥，后序
if(len <= 0) return -1;
if(len == 1) {
node[++tot].val = b[1];
node[tot].l=node[tot].r = -1;
return tot;
}
node[++tot].val = c[len];
int res = tot;
int l;
for(l = 1; l<=len; l++) { //找到切割點(diǎn)
if(b[l] == c[len]) break;
}
node[res].l = dfs(l-1,b,c);//進(jìn)去后 node[res].r = dfs(len-l,b+l-1,c+l);
node[res].r = dfs(len-l,b+l,c+l-1);
return res;
}
void bfs() { //層序遍歷
queue<int> q;
q.push(1);
while(q.size()) {
int cur = q.front();
q.pop();
if(cur != 1) printf(" ");
printf("%d",node[cur].val);
if(node[cur].l != -1) q.push(node[cur].l);
if(node[cur].r != -1) q.push(node[cur].r);
}
}
int main()
{
int n;
cin>>n;
for(int i = 1; i<=n; i++) scanf("%d",c+i);
for(int i = 1; i<=n; i++) scanf("%d",b+i);
dfs(n,b,c);
bfs(); //在這里有打印操作
return 0 ;
}
【7-10 PAT】樹的遍歷（給定一棵二叉樹的后序遍歷和中序遍歷，請(qǐng)你輸出其層序遍歷的序列茂蚓。）
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門疑枯，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人蛔六，你說(shuō)我怎么就攤上這事荆永。” “怎么了古今？”我有些...
- 文/不壞的土叔 我叫張陵屁魏，是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我捉腥，道長(zhǎng)氓拼，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任抵碟，我火速辦了婚禮桃漾，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘拟逮。我一直安慰自己撬统，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布敦迄。 她就那樣靜靜地躺著恋追，像睡著了一般。 火紅的嫁衣襯著肌膚如雪罚屋。 梳的紋絲不亂的頭發(fā)上苦囱，一...
- 那天，我揣著相機(jī)與錄音脾猛，去河邊找鬼撕彤。 笑死，一個(gè)胖子當(dāng)著我的面吹牛猛拴，可吹牛的內(nèi)容都是我干的羹铅。 我是一名探鬼主播蚀狰，決...
- 文/蒼蘭香墨 我猛地睜開眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼职员！你這毒婦竟也來(lái)了麻蹋？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬(wàn)榮一對(duì)情侶失蹤廉邑，失蹤者是張志新（化名）和其女友劉穎哥蔚，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蛛蒙，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡糙箍，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了牵祟。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片深夯。...
- 正文 年R本政府宣布掌呜，位于F島的核電站，受9級(jí)特大地震影響坪哄，放射性物質(zhì)發(fā)生泄漏质蕉。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一翩肌、第九天 我趴在偏房一處隱蔽的房頂上張望模暗。 院中可真熱鬧，春花似錦念祭、人聲如沸兑宇。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)隶糕。三九已至，卻和暖如春站玄，著一層夾襖步出監(jiān)牢的瞬間若厚，已是汗流浹背。 一陣腳步聲響...
- 正文 我出身青樓灾常，卻偏偏與公主長(zhǎng)得像霎冯，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子钞瀑，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 題目 1020 Tree Traversals （25 分）Suppose that all the keys i...
- 二叉樹附demo，前序遍歷螟蒸、后序遍歷盒使、層序遍歷、刪除一個(gè)二叉樹的節(jié)點(diǎn)七嫌，前驅(qū)后繼節(jié)點(diǎn)等概念啊和原理 demo 基本概...
