[luogu p1827] [USACO3.4]美國血統 American Heritage

傳送門

[USACO3.4]美國血統 American Heritage

題目描述

農夫約翰非常認真地對待他的奶牛們的血統。然而他不是一個真正優秀的記帳員。他把他的奶牛 們的家譜作成二叉樹，并且把二叉樹以更線性的"樹的中序周遊"和"樹的前序周遊"的符号加以記錄而 不是用圖形的方法。

你的任務是在被給予奶牛家譜的"樹中序周遊"和"樹前序周遊"的符号後，建立奶牛家譜的"樹的 後序周遊"的符号。每一頭奶牛的姓名被譯為一個唯一的字母。(你可能已經知道你可以在知道樹的兩 種周遊以後可以經常地重建這棵樹。)顯然，這裡的樹不會有多于 26 個的頂點。 這是在樣例輸入和 樣例輸出中的樹的圖形表達方式：

C
　　　　　　   /  \
　　　　　　  /　　\
　　　　　　 B　　  G
　　　　　　/ \　　/
　　　　   A   D  H
　　　　　　  / \
　　　　　　 E   F
           

樹的中序周遊是按照左子樹，根，右子樹的順序通路節點。

樹的前序周遊是按照根，左子樹，右子樹的順序通路節點。

樹的後序周遊是按照左子樹，右子樹，根的順序通路節點。

輸入輸出格式

輸入格式

第一行： 樹的中序周遊

第二行： 同樣的樹的前序周遊

輸出格式

單獨的一行表示該樹的後序周遊。

輸入輸出樣例

輸入樣例 #1

ABEDFCHG
CBADEFGH
           

輸出樣例 #1

AEFDBHGC
           

說明

題目翻譯來自NOCOW。 USACO Training Section 3.4

分析

這題真的和luogu p1030賊像。(點連結檢視那道題的題解)

是以我直接把代碼複制過來，改了改，交上去了。

這題和luogu p1030的唯一差別是，原題是給中後求先，此題是給中先求後。但是基本思路都是一樣的，先序周遊找根，中序周遊遞歸左右子樹。

和那道題相比，需要改動的地方：

• 先work函數，再輸出根。(後序周遊輸出順序左右根)
• 根不再是

  s2[s2.length() - 1]

  而是

  s2[0]

  ，因為先序周遊中第一個字元就是根。
• 注意遞歸的左右邊界。s1參數不用改，況且都是中序周遊，s2參數中，因為根在第一個，是以左子樹在先序周遊字元串中的範圍應該是1pos+1，右子樹在先序周遊字元串中的範圍應該是pos+1s2.length()。代碼應該改為：

  work(s1.substr(0, pos), s2.substr(1, pos));
    work(s1.substr(pos + 1), s2.substr(pos + 1));
             

是以和那道題相比，這道題的代碼其實變簡單了……

那就，直接上代碼！

代碼

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2020-07-19 23:19:35 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2020-07-20 00:33:51
 */
#include <iostream>
#include <cstdio>

void work(std :: string s1, std :: string s2) {
    if(s1.size() == 0) return ;
    char root = s2[0];
    int pos = s1.find(root);
    work(s1.substr(0, pos), s2.substr(1, pos));
    work(s1.substr(pos + 1), s2.substr(pos + 1));
    std :: cout << root;
}

int main() {
    std :: string s1, s2;
    std :: cin >> s1 >> s2;
    work(s1, s2);
    return 0;
}
           

評測記錄

評測記錄