人才网站建设标题,不花钱网站推广,做网站如何防止被抄袭,计算机网站建设文献综述题目链接#xff1a;P1827 [USACO3.4] 美国血统 American Heritage - 洛谷 | 计算机科学教育新生态
题目难度#xff1a;普及 首先介绍下二叉树的遍历#xff1a; 学过数据结构都知道二叉树有三种遍历#xff1a; 1.前序遍历#xff1a;根左右 2.中序遍历#xff1a;左根…题目链接P1827 [USACO3.4] 美国血统 American Heritage - 洛谷 | 计算机科学教育新生态
题目难度普及 首先介绍下二叉树的遍历 学过数据结构都知道二叉树有三种遍历 1.前序遍历根左右 2.中序遍历左根右 3.后序遍历左右根 解题思路 前序遍历是先遍历根节点再遍历根节点的左右子树。那么前序序列的第一个节点一定是根 节点。找到根节点再确定根节点在中序序列中的位置就可以分出左右两棵子树。这道题就可以不用建树直接递归来求就好了 下面奉上代码部分 #include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 1e6 10;
string front, middle;void dfs(string front, string middle)
{// 如果前序遍历为空说明没有节点直接返回if (front.size() 1) return;// 找到当前根节点在中序遍历中的位置int t middle.find(front[0]);// 递归处理左子树前序遍历从1开始长度是t中序遍历是前t个字符dfs(front.substr(1, t), middle.substr(0, t));// 递归处理右子树前序遍历从t1开始长度是front.size() - t - 1中序遍历是从t1到结尾dfs(front.substr(t 1, front.size() - t - 1), middle.substr(t 1, front.size() - t - 1));// 输出当前节点先序遍历的根节点cout front[0];
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin middle front;//注意题目要求先输入中序然后是前序 dfs(front, middle);return 0;
}
