题解 P1827 【美国血统 American Heritage】

· · 题解

这道题难道就没有人用链表的吗？那我就来发(shui)一篇用链表做的题解。那么，这道题怎么确定二叉树的每个节点呢？方法如下， 就拿样例来说：

ABEDFCHG
CBADEFGH

这棵二叉树的根节点为C，就将根节点插入链表，根节点在中序遍历的第n个，就递归向下n-1个，剩余的也递归，一次之后，这棵树变成这个样子：

[ABEDF]C[HG]
C[BADEF][GH]

最终，这棵树成这个样子：

[[A]B[[E]D[F]]]C[[H]G]
C[B[A][D[E][F]]][G[H]]

后序遍历即为：

AEFDBHGC

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{//链表
    char val;
    node *l,*r;
};
node *root;
char prv[30],ord[30];
void init(int sp,int ep,int so,int eo,node *&p){//建立二叉树
    if(sp>ep||so>eo) return;
    int i,j;
    for(i=sp,j=so;i<=ep;++i,++j)
        if(ord[j]==prv[sp])
            break;
    p=new node;
    p->l=p->r=NULL;//注意每一次在申请空间之后，左右子节点都要变成空节点，否则会RE
    p->val=prv[sp];
    init(sp+1,i,so,j-1,p->l);//递归
    init(i+1,ep,j+1,eo,p->r);
}
void dfs(node *p){//后序遍历
    if(p==NULL) return;//如果该节点为空，直接返回
    dfs(p->l),dfs(p->r);
    putchar(p->val);
}
int main(){
    scanf("%s%s",ord,prv);
    init(0,strlen(prv)-1,0,strlen(ord)-1,root);
    dfs(root);
    return 0;
}