153. 已知先序周遊和中序周遊，求二叉樹的後序周遊

題目描述

有一棵二叉樹，每個節點由一個大寫字母辨別(最多26個節點）。現有兩組字母，分别表示前序周遊（父節點->左孩子->右孩子）和中序周遊（左孩子->父節點->右孩子）的結果，請你輸出後序周遊（左孩子->右孩子->父節點）的結果。

解答要求時間限制：1000ms, 記憶體限制：100MB

輸入

每個輸入檔案包含兩串字母，各占一行。（每串隻包含大寫字母）

第一行字母表示前序周遊結果，第二行字母表示中序周遊結果。

輸出

輸出僅一行，表示後序周遊的結果，結尾換行。

樣例

輸入樣例 1 複制

DBACEGF
ABCDEFG      

輸出樣例 1

ACBFGED      

提示樣例 1

提示

思路：先從先序周遊中找到根節點，然後從中序周遊中找到左子樹和右子樹，遞歸，建構二叉樹，最後再進行後序周遊。

// we have defined the necessary header files here for this problem.
// If additional header files are needed in your program, please import here.
#include<iostream>
using namespace std;
#include<string.h>
struct TreeNode//定義二叉樹
{
    TreeNode* left;
    TreeNode* right;
    char val;
    TreeNode(char v):val(v),left(NULL),right(NULL){}
};
TreeNode*constructTree(string Preorder,string Inorder)//根據中序和先序建構二叉樹
{
    if(Preorder.size()==0)
    {
        return NULL;
    }
    char midval = Preorder[0];
    TreeNode*root = new TreeNode(midval);
    if(Preorder.size() == 1)
    {
        return root;
    }
    int midx = 0;
    for(;midx<Preorder.size();midx++)
    {
        if(midval == Inorder[midx])
        {
            break;
        }
    }
    string pre_left = Preorder.substr(1,midx);
    string pre_right = Preorder.substr(midx+1);
    string In_left = Inorder.substr(0,midx);
    string In_right = Inorder.substr(midx+1);
    root->left = constructTree(pre_left,In_left);
    root->right = constructTree(pre_right,In_right);
    return root;
}
void lastorder(TreeNode*Node)//輸出後序周遊
{
      if(Node == NULL)
      {
          return;
      }
    lastorder(Node->left);
    lastorder(Node->right);
    cout<<Node->val;
}
int main()
{
    // please define the C input here. For example: int n; scanf("%d",&n);
    // please finish the function body here. 
    // please define the C output here. For example: printf("%d\n",a);
    string pre,in;
    cin>>pre>>in;
    TreeNode*root = constructTree(pre,in);
    lastorder(root);
    return 0;
}      

以大多數人努力程度之低，根本輪不到去拼天賦~