美国血统

洛谷P1827

Hi 最近我爱上二叉树了… 来 看看这个

唉 题目真么绕 不就是给先序中序求后序嘛 如果你刚刚学二叉树 推荐看看这两道题哦～ 二叉树讲解+二叉树深度 后缀表达式

好了 这道题不难 直接这样写吧

//
//  main.cpp
//  美国血统
//
//  Created by Helen on 2020/8/13.
//  Copyright © 2020 Helen. All rights reserved.
//
//感谢洛谷@Bartholomew提供思路#include <iostream>
#include <string>
using namespace std;
string mid,pre; // 先序&中序数组
int l,a; 
void dfs(int px,int py,int mx,int my);
int main ()
{cin >> mid >> pre; // 输入 别忘了是先中序啊！l=mid.length()-1; // 长度...dfs(0,l,0,l); // 传入变量...
}
void dfs(int px,int py,int mx,int my) // px&py=先序数组的范围 mx&my=中序数组的范围 
{if (mx>my || px>py) // 如果超出范围了return; // 返回...int a=mid.find(pre[px]); // 在中序数组中找先序的第px个dfs(px+1,px+a-mx,mx,a-1); // 遍历左子树...dfs(px+a-mx+1,py,a+1,my); // 右子树...cout << pre[px]; // 输出当前找的那个点
}