24h購物| | PChome| 登入
2012-06-02 17:52:11| 人氣3,813| 回應20 | 上一篇 | 下一篇

[UVA] 10701 - Pre, in and post

推薦 0 收藏 0 轉貼0 訂閱站台

Problem F - Pre, in and post

Time Limit: 1 second

A common problem in data structures is to determine the traversal of a binary tree. There are three classic ways to do it:

Pre-order: You must visit in sequence the root, left subtree and the right subtree.
In-order: You must visit in sequence the left subtree, the root and the right subtree.
Post-order: You must visit in sequence the left subtree, the right subtree and the root.

See the picture below:

graph.png

The pre, in and post-order traversal are, respectively,  ABCDEF, CBAEDF and CBEFDA. In this problem, you must compute the post-order traversal of a binary tree given its in-order and pre-order traversals.

Input

The input set consists of a positive number C ≤ 2000, that gives the number of test cases and C lines, one for each test case. Each test case starts with a number 1 ≤ N ≤ 52, the number of nodes in this binary tree. After, there will be two strings S1 and S2 that describe the pre-order and in-order traversal of the tree. The nodes of the tree are labeled with different characters in the range a..z and A..Z. The values of N, S1 and S2 are separeted by a blank space.

Output

For each input set, you should output a line containing the post-order transversal for the current tree.

Sample input

3
3 xYz Yxz
3 abc cba
6 ABCDEF CBAEDF

Sample output

Yzx
cba
CBEFDA


這東西很久沒寫, 都快忘光了

#include <stdio.h>
char a[60], b[60];
int idx;
void find(int l, int r) {
    if(l > r)   return;
    int i;
    for(i = l; i <= r; i++) {
        if(b[i] == a[idx])
            break;
    }
    if(i != r+1) {
        idx++;
        find(l, i-1);
        find(i+1, r);
        putchar(b[i]);
    }
}
int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %s %s", &n, a, b);
        idx = 0;
        find(0, n-1);
        puts("");
    }
    return 0;
}

台長: Morris
人氣(3,813) | 回應(20)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][最大生成樹] 1234 - RACING
此分類上一篇:[UVA][中國郵路問題] 117 - The Postal Worker Rings Once

remove password in window 10
somebody told me that we can remove password of any PC. I did not believe him. since I visit here https://removepasswordwindows10.xyz
I realise that his words are true. Now I can remove password of any system and use it.
2019-06-18 18:08:52
Whirlpool AWOD 6528
I ran your script on my laptop and now it doesn’t turn on :(
2019-08-21 03:10:49
喵~
不錯的文章分享

----------------------------------------
小鴨影音 http://eet.cc/
2020-08-02 02:30:26
fiction book writing services
Thank you regarding offering latest revisions about the problem, My partner and i enjoy examine a lot more. fiction book writing services https://writersofthewest.net/fiction-writing-services/
2023-11-02 22:11:01
Best Seminyak Restaurant
Wonderful Content, Now i'm a massive believer for offer suggestions relating to internet websites to make sure you let the web page creators understandthat they’ve incorporated an issue good to make sure you just a couple of! Best Seminyak Restaurant https://foodparadise.network/seminyak-best-restaurants-cafes/
2023-11-08 16:53:55
seo
Definitely stable, brilliant, fact-filled facts in this article. Ones threads Do not sadden, and this absolutely is true in this article likewise. People generally produce a motivating understand. Would you say to Now i am fascinated?: )#) Sustain the great articles or blog posts. UFABETสมัครแทงบอลฟรีไม่มีขั้นต่ำ http://www.marco-island-realestate.com/ufabetสมัครแทงบอลฟรีไม่มีขั้นต่ำ/
2024-01-24 20:47:53
savvybudge
I have read your article, it is very informative and helpful for me.I admire the valuable information you offer in your articles. Thanks for posting it.. UFABETเว็บบอลคนเล่นเยอะสุด http://www.victoriarealestate.net/ufabetเว็บบอลคนเล่นเยอะสุด/
2024-01-28 20:29:09
gaib4d
Amazing! Exactly what a watch opener this particular publish may be personally. Greatly valued, saved, We can’t await much more! 이미테이션 사이트 https://e-dith.net/
2024-02-01 18:52:51
Faddy
I went over this website and I believe you have a lot of wonderful information, saved to my bookmarks 명품 짝퉁 http://cheep957.com/
2024-02-01 21:50:59
Harrison21
Ordinary comes to visit and listed below are one way to thanks for your time for one's exertion, which inturn means that So i'm seeing this website every single day, hunting for unique, important tips. A number of, many thanks! 상품권 교환 https://pandapin365.com/
2024-02-04 20:43:02
aaaa
I admire what you have done here. I like the part where you say you are doing this to give back but I would assume by all the comments that this is working for you as well..홍대가라오케 https://www.hongdae517.com/
2024-02-04 22:48:27
Harrison21
I’m influenced using the surpassing as well as preachy itemizing that you simply provide such small timing. explorer le canada autochtone à travers son tourisme http://www.canada-eta-visa.org/fr/explorer-le-canada-autochtone-à-travers-son-tourisme/
2024-02-10 19:03:09
Harrison21
This is usually a wonderful recommendations primarily so that you can all those a novice to blogosphere, limited plus genuine information… With thanks to get spreading brussels. Very important learn posting. Bahis Siteleri https://bombabahis.com/
2024-02-12 19:28:23
Harrison21
Everything has its value. Thanks for sharing this informative information with us. GOOD works! modems http://timebusinessnews.com/top-10-must-have-software-for-everyday-consumer-computing/
2024-02-12 21:47:49
Harrison21
Thanks a ton to get writing this sort of superb posting! I uncovered your web blog ideal for this demands. Contained in the grapefruit excellent plus handy discussions. Keep up to date favorable deliver the results! Kaçak bahis siteleri http://www.betcinim.com/
2024-02-14 18:00:09
Harrison21
Normal appointments listed here are the easiest method to thanks for the work, that means that I am going to the website daily, searching for brand new, fascinating data. Numerous, thank you! บาคาร่า เว็บตรง http://rudee11.com/
2024-02-15 17:26:03
seo
I'd personally declare that will this is the a terrific article of an wonderful man or woman, i am just very happy to discover this specific. buy ambien online http://meridian-pharm.com/product-category/buy-ambien-online/
2024-02-17 17:49:48
jun88
New web site is looking good. Thanks for the great effort. jun88 http://jun88.luxury/
2024-02-20 19:41:27
Harrison21
I'd personally declare that will this is the a terrific article of an wonderful man or woman, i am just very happy to discover this specific. Natural Electrolyte Drinks http://www.healthkept.com/natural-electrolyte-drinks-for-post-workout-hydration/
2024-03-03 18:31:51
Harrison21
Great post. The particular submit has an effect on plenty of important difficulties individuals community. We all can't be uninvolved to be able to these kinds of difficulties. This kind of submit offers guidelines and also principles. Extremely useful and also sensible. AustralianCitizenshipSupport http://citizenshiptests.au/
2024-03-03 21:37:33
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文