二叉樹結構 codevs 1029 遍歷問題

codevs 1029 遍歷問題

?時間限制: 1 s

?空間限制: 128000 KB

?題目等級 : 鉆石 Diamond

題目描述?Description

?? ?我們都很熟悉二叉樹的前序、中序、后序遍歷，在數據結構中常提出這樣的問題：已知一棵二叉樹的前序和中序遍歷，求它的后序遍歷，相應的，已知一棵二叉樹的后序遍歷和中序遍歷序列你也能求出它的前序遍歷。然而給定一棵二叉樹的前序和后序，你卻不能確定其中序遍歷序列，考慮如下圖中的幾棵二叉樹：

?? ?所有這些二叉樹都有著相同的前序遍歷和后序遍歷，但中序遍歷卻不相同。

輸入描述?Input Description

?? ?輸入文件共2行，第一行表示該樹的前序遍歷結果，第二行表示該樹的后序遍歷結果。輸入的字符集合為{a-z}，長度不超過26。

輸出描述?Output Description

?? ?輸出文件只包含一個不超過長整型的整數，表示可能的中序遍歷序列的總數。

樣例輸入?Sample Input

abc

cba

樣例輸出?Sample Output

 1 /*雖然題目說要用樹形DP或者搜索，但是如果對樹的結構了解夠深的話，也可以直接做。
 2 很明顯，已知一棵二叉樹的前序遍歷和后序遍歷，判斷中序遍歷時，其可能性只與沒有兄弟節點的葉節點的位置有關。
 3 假設沒有兄弟節點的葉節點共有n個，則可能性邊有2^n個。（就不證明了）
 4 那么，如何計算n的值呢？
 5 下面有一個性質：
 6 一棵二叉樹的前序遍歷a1a2a3...ai和后序遍歷b1b2b3...bi有一種關系：
 7 沒有兄弟節點的葉節點的根 在a序列下標為i， 在b序列下標為j
 8 則有  a[i-1] == b[j+1]
 9 這是因為當根只有一棵子樹時，前序和后序遍歷都是先遍歷它的孩子，而且是唯一的一個孩子，所以相對位置是一樣的。
10 */
11 #include<iostream>
12 using namespace std;
13 string pre,hou;
14 int lenpre,lenhou;
15 int ans=0;
16 int main()
17 {
18     cin>>pre>>hou;
19     lenpre=pre.length()-1;
20     lenhou=hou.length()-1;
21     for(int i=1;i<=lenpre;++i)
22       for(int j=0;j<=lenhou-1;++j)
23       if(pre[i]==hou[j]&&pre[i-1]==hou[j+1])
24       ans++;
25     cout<<(long long)(1<<ans)<<endl;
26     return 0;
27 }

轉載于:https://www.cnblogs.com/c1299401227/p/5573830.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/287406.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/287406.shtml
英文地址，請注明出處：http://en.pswp.cn/news/287406.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！