☘前言☘
今日份水题开始。希望有想要提高的同学跟我们一起来刷题0.0
4.12日每日一题——美国血统
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
解题思路
📑写在最后
P1827 [USACO3.4] 美国血统 American Heritage
解题思路
这部分其实是考研的重点，太长时间不用都快忘记了，其实思路就是分割字符串，比如给的样例。
ABEDFCHG
CBADEFGH
分割之后的样子就应该是：
[ABEDF]C[HG]
C[BADEF][GH]
这个对应着代码去看下标就能理解了。
#include <cstdio>
#include <cstring>
#include <cstdlib>
struct node{ char val; struct node *left, *right; }; struct node *noot; char zhongxu[30], prev[30]; void create(int zleft, int zright, int pleft,int pright,node **root){//生成树 if(zleft > zright || pleft > pright) return;//直接就是空啦 int i,j; for(i = pleft, j = zleft;i < pright;i++,j++) //查找分割点 if(zhongxu[j] == prev[pleft]) break; (*root) = (struct node *)malloc(sizeof(struct node)); //建立节点 node *p = *root; p->val = prev[pleft]; p->left = p->right = NULL; create(zleft,j-1,pleft+1, i,&p->left); //创建左子树 create(j+1,zright,i+1,pright,&p->right); //创建右子树 } void hou(node *p){ //后续遍历 if(p){ hou(p->left); hou(p->right); putchar(p->val); } } int main(){ scanf("%s %s",zhongxu,prev); node *root; create(0,strlen(zhongxu) - 1,0, strlen(prev) - 1,&root); hou(root); }
