復原二叉樹

時間限制:?1 Sec??內(nèi)存限制:?128 MB

題目描述

小明在做數(shù)據(jù)結(jié)構(gòu)的作業(yè)，其中一題是給你一棵二叉樹的前序遍歷和中序遍歷結(jié)果，要求你寫出這棵二叉樹的后序遍歷結(jié)果。

輸入

輸入包含多組測試數(shù)據(jù)。每組輸入包含兩個字符串，分別表示二叉樹的前序遍歷和中序遍歷結(jié)果。每個字符串由不重復的大寫字母組成。

輸出

對于每組輸入，輸出對應的二叉樹的后序遍歷結(jié)果。

樣例輸入

DBACEGF ABCDEFG BCAD CBAD

樣例輸出

ACBFGED CDAB

已知二叉樹的先序與中序，輸出后序

前序最先出現(xiàn)總是根結(jié)點，root為前序中當前的根結(jié)點下標，并且同時在中序把二叉樹分為左子樹和右子樹
start為當前需要打印的子樹在中序中的最左邊的下標，end 為當前需要打印的子樹在中序中最右邊的下標

//已知二叉樹的先序與中序，輸出后序 /* 前序最先出現(xiàn)總是根結(jié)點，root為前序中當前的根結(jié)點下標 并且同時在中序把二叉樹分為左子樹和右子樹 start為當前需要打印的子樹在中序中的最左邊的下標， end 為當前需要打印的子樹在中序中最右邊的下標， */ #include<bits/stdc++.h> using namespace std; string pre;//前序 string in; //中序 void post(int root,int start,int end) {//遞歸打印這棵樹的后序，遞歸出口為 start > endif(start>end)return;int i=start;//i為 root所代表的值在中序中的下標while(i<end&&in[i]!=pre[root])i++;int cnt=i-start;//左子樹結(jié)點個數(shù)post(root+1,start,i-1);post(root+1+cnt,i+1,end);printf("%c",pre[root]);}int main(){while(cin>>pre>>in){int len=pre.length();post(0,0,len-1);printf("\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的复原二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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