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;
}      

以大多数人努力程度之低，根本轮不到去拼天赋~