P1030 [NOIP 2001 普及组] 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ）。

输入格式

共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串，表示一棵二叉树的先序。

输入输出样例 #1

输入 #1

BADC
BDCA

输出 #1

ABCD

说明/提示

【题目来源】

NOIP 2001 普及组第三题

这道题要求根据中序遍历和后序遍历结果求先序遍历字符串，那最直接的想法自然就是还原这棵树，再先序遍历。

我们清楚，中序遍历的规则是“左-根-右”，后序遍历的规则是“左-右-根”。

例如：中序遍历为BADC，后序遍历为BDCA。

后序遍历结果的末尾A为根节点，同时，对应到先序遍历结果里，A划分它的左右子树B和DC。
同时，在后序遍历去除A的结果里，BDC分别为左子树的后序遍历B和右子树的后序遍历DC，则可以套用前理。
则，我们可以发现，中序遍历里，每个根节点都将剩余部分划分为左右子树的中序遍历；后序遍历里，每个根节点去除后就是左右子树的后序遍历，且左子树的后序遍历固定在右子树的后序遍历之前。

由此，我们可以利用分治的思想，还原这棵树。 具体代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
using namespace std;
struct TNode{
    char val;
    TNode *Lchid,*Rchid;
    TNode(char v):val(v),Lchid(nullptr),Rchid(nullptr){};
};
TNode* PreTree(string ins,stack<char> &st);
void prit(TNode *root);
int main(){
    string ins,posts;
    cin>>ins;
    cin>>posts;
    stack<char> st;
    for(char val:posts) st.push(val);	//将后序遍历结果依次存入栈
    TNode *root=PreTree(ins,st);
    prit(root);
    return 0;
}
TNode* PreTree(string ins,stack<char> &st){
    if(ins.size()<=0 || st.empty()) return nullptr;
    char ch=st.top();
    st.pop();
    TNode *root=new TNode(ch);
    int rootix=ins.find(ch);	//找到根节点再中序遍历的位置，划分左右子树
  	//因为后序遍历是“左-右-根”，在进行逆处理时反过来，按照“根-右-左”顺序
    root->Rchid=PreTree(ins.substr(rootix+1,ins.size()-rootix-1),st);
    root->Lchid=PreTree(ins.substr(0,rootix),st);
    return root;
}
void prit(TNode *root){
    if(root){
        printf("%c",root->val);
        prit(root->Lchid);
        prit(root->Rchid);
    }
}