首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

這題是我最初還沒學到關於存取二元樹的時候(那時候還只會用Adjacency list)，很想解的一題
後來在書上看到使用中序、先序求後序走訪的作法，便在學透那個章節後，自己來推一下
AC後真的信心增加很多(太多比賽被電到飛起來QQ)

解題想法

有點複雜喔 沒有很難 安全帶繫好:D

既然給了二元樹的中序走訪、後序走訪，那麼就要先來想想走訪的概念。(說錯歡迎指教<3)
preorder(先序走訪) : 父節點->左子樹->右子樹
inorder(中序走訪) : 左子樹->父節點->右子樹
postorder(後序走訪) : 左子樹->右子樹->父節點
(存取圖的部分我使用結構搭配指標)
接下來是最重要的部分，用一個函式透過inorder、postorder來建造二元樹再存取起來(結構new node)
我使用後序的字串來切割中序，再不停遞迴右子樹再左子樹(為什麼先右子樹是我解題的關鍵，可以自己推推看)
一開始我是先宣告一個結構當作根節點，再呼叫建造二元樹的函式，就能一直開創根節點的左子樹的左..(右子樹也是喔)
最後再透過前面結構開創的空間，從root開始先序走訪和輸出就好囉(判斷NULL的部分要注意喔)

AC code

#include<bits/stdc++.h>
using namespace std;
struct node{
    char data;
    struct node*left;//指標指向左子樹
    struct node*right;//指標指向右子樹
};
string ino,post;
int len,first;//字串長度，用於提取剩下的字元(即樹的節點)
void preorder(node*);//二元樹先序輸出
node* buildTree(int ,int );//建造二元樹的函式
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> ino >> post;
    len=ino.size();
    first=len-1;
    // cout << len << " " << first << endl;     
    node* root;
    root=buildTree(0,len-1);
    preorder(root);
    cout << endl;
    return 0;
}
void preorder(node *p){
    if(p!=NULL){
        cout << p->data;
        preorder(p->left);
        preorder(p->right);
    }
}
node *buildTree(int left,int right){
    int mid;
    node *bNode;
    bNode=new node;//開創新空間
    if(first>=0){
        bNode->data=post[first--];//拿取後序字串
        if(left<right){
            for(int x=left;x<=right;x++){
                if(ino[x]==bNode->data){
                    mid=x;
                    break;
                }
            }
            //右子樹先(後序走訪的特性)
            if(right>mid){
                bNode->right=buildTree(mid+1,right);
            }
            else{
                bNode->right=NULL;
            }
            //在左子樹
            if(left<mid){
                bNode->left=buildTree(left,mid-1);
            }
            else{
                bNode->left=NULL;
            }
        }
        //葉節點出現
        else{
            bNode->left=NULL;
            bNode->right=NULL;
        }
        return bNode;
    }
}

題目連結 : NOIP2001 3.先序排序

Run server

$ hexo server

More info: Server