题目大意：给出二叉树的先序和后序序列，判断能否构成一棵唯一的二叉树。并输出中序遍历的结果。
与常规问题不同，需要考虑怎么从先序和后序序列中得到左右子树。例如，先序序列的范围是[ prel, prer ]，后序序列的范围是[ postl, postr ]，那么，显然 prel 和 postr 对应的都是当前树的根节点 root，[prel +1, prer] 包含左右子树，prel + 1是左或右子树的根节点； [postl, postr-1]包含左右子树，postr - 1是左或右子树的根节点。如果 prel +1 和 postr - 1 对应的不是一个节点，说明左子树和右子树都存在；否则说明剩下的节点全在一棵子树上，就无法确定是左子树还是右子树，从而不唯一。如果 prel + 1 和 posrt -1 对应的不是同一个节点，那么在后序序列中找到 与prel + 1对应的节点，从它往左就是左子树（含它本身），从它往右就是右子树(不含它本身)，从而可以进行递归。
这里要注意如果左右子树只存在一棵的话，左子树的节点数量如果用先遍历再减法的方式可能会算错，需要在遍历查找时累加左子树的节点数量，避免错误。另外一个坑点是必须在结尾必须输出换行符，否则会格式错误。
AC代码：
#include <vector>
#include <cstdio>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
Node(int data):data(data), left(NULL), right(NULL){};
};
vector<int> pre;
vector<int> post;
bool determined = true;
Node* root = NULL;
void createFromPrePost(Node* &node, int prel, int prer, int postl, int postr)
{
if(prel > prer) return;
if(node == NULL) node = new Node(pre[prel]);
int index = postl, leftNum = 0;
for (index = postl; index < postr; ++index)
{
leftNum++;
if(post[index] == pre[prel + 1]) break;
}
if(index == postr - 1) determined = false;
createFromPrePost(node->left, prel+1, prel+leftNum, postl, index);
createFromPrePost(node->right, prel+leftNum+1, prer, index+1, postr-1);
}
void inOrder(Node* node, int N)
{
static int printCnt = 0;
if(node->left) inOrder(node->left, N);
printf("%d", node->data);
if(++printCnt < N) printf(" ");
else printf("\n");
if(node->right) inOrder(node->right, N);
}
int main()
{
int N;
scanf("%d", &N);
pre.resize(N);
post.resize(N);
for (int i = 0; i < N; ++i)
scanf("%d", &pre[i]);
for (int i = 0; i < N; ++i)
scanf("%d", &post[i]);
createFromPrePost(root, 0, N-1, 0, N-1);
if(determined) printf("Yes\n");
else printf("No\n");
inOrder(root, N);
return 0;
}
文章浏览阅读722次。js文件类型、大小验证方法/** * 验证文件类型 * @param fileInputElementId 文件标签id * @param fileType 文件类型 * @returns Y - 文件类型与指定的fileType一致，N - 不一致，E - 文件为空 */function validateFileType(fileInputElementId, fileTy..._js校验文件大小
文章浏览阅读535次。语言特性1.谈谈对 Python 和其他语言的区别答：Python属于比较"自由”的语言，首先变量使用前不需要声明类型，其次语句结束不需要使用分号作为结尾，同时不需要大括号进行代码块的标注，使用缩进对大括号进行代替。2.简述解释型和编译型编程语言答：编译型语言是将代码编译成机器码，然后执行，通过编译可以使得程序直接以机器码的形式进行工作。通俗一点就是将整个程序一次性编译后再执行。解释型语..._python爬虫面试题
文章浏览阅读1.6k次。网上基本上都是import引入el-image-viewer这个隐藏小组件但是现在是在原来非vue项目里要用到这个预览功能尝试了半天，cdn也没办法引入这个组件。然后看到有分析这个组件源码，点击img，是执行了clickHandler方法。且判断依据是showViewer= !0的时候，将这一句改为：showViewer: !0效果实现。如果有机会，我还是想知道如何cdn引入按需这个小组件的…..._el-image 默认文字
文章浏览阅读843次。0 写在前面最近看到一篇CSDN，里面巧妙运用了字典的引用传递和dict.setdefault(key, default=None)方法，有点绕打算细细记录一下。本篇的中心思想在于实现字典嵌套方面。1 一马当先首先看如下demodata = {}tmp = {'b': 1}data['a'] = tmpprint(data) # {'a': {'b': 1}}以上是没有使用引..._dict引用套娃
文章浏览阅读1.1w次，点赞3次，收藏21次。开始---->运行---->cmd，或者是window+R组合键，调出命令窗口输入命令：netstat -ano，列出所有端口的情况。查找8080端口打开任务管理器：Ctr+Alt+. 或 Ctr+Shift+Esc看找 PID ： 47645. 右键，结束任务..._8080端口查看
文章浏览阅读921次。几个分形的matlab实现摘要：给出几个分形的实例，并用matlab编程实现方便更好的理解分形，欣赏其带来的数学美感关键字：Koch曲线 实验 图像一、问题描述：从一条直线段开始，将线段中间的三分之一部分用一个等边三角形的两边代替，形成山丘形图形如下图1在新的图形中，又将图中每一直线段中间的三分之一部分都用一个等边三角形的两条边代替，再次形成新的图形如此迭代，形成Koch分形曲线。 二、算..._分形代码maltarb
文章浏览阅读7.9k次，点赞9次，收藏154次。文章目录概述dwatebtrajectory概述概述参考在ROS中，进行导航需要使用到的三个包是：（1） move_base：根据参照的消息进行路径规划，使移动机器人到达指定的位置；（2） gmapping：根据激光数据（或者深度数据模拟的激光数据）建立地图；（3） amcl：根据已经有的地图进行定位。*在总体框架图中可以看到，move_base提供了ROS导航的配置、运行、交互接..._ros 局部地图计算
文章浏览阅读513次。项目虽然是采用 React Native 开发的，但是实际使用体验应该不输大部分 Github 上的个人开发的原生应用。安装依赖及运行安装依赖pip install -r requirements.txt数据库初始化python manage.py db init本地运行python manage.py runserver -h0.0.0.0 -p80服务器部署第一步：新增环境变量export f..._php手机论坛推荐
文章浏览阅读913次。1 HikariCPHikariCP 来源于日语，「光」的意思，意味着它很快！可靠的数据源，spring boot2.0 已经将 HikariCP 做为了默认的数据源链接池。官网详细地说明了HikariCP所做的一些优化，总结如下：字节码精简 ：优化代码，直到编译后的字节码最少，这样，CPU缓存可以加载更多的程序代码；优化代理和拦截器：减少代码，例如 HikariCP 的 Statement proxy 只有 100 行代码，只有BoneCP 的十分之一；自定义数组类型（FastStatement_包括hikaricp依赖
文章浏览阅读4k次，点赞3次，收藏6次。package ppt10lang包;/* String s=”name=zhangsan age=18 classNo=090728”; 将上面的字符串拆分，结果如下: zhangsan 18 090728 1)第一次split," " 2)进行遍历 3)第二次split, =，每次只要取新数组的下标1的内容就够了 */public class L..._string s=”name=zhangsan age=18 classno=090728”; 将上面的字符串拆分,结果如
文章浏览阅读5.2k次，点赞5次，收藏35次。C++与Python之间跨进程通信（socket实现）1.引言2.实现思路3. 具体代码（1）Python服务端（2）C++客户端1.引言之前写过一篇Python调用C++程序的实现方法，这里相反，希望使用Python协助C++完成某些任务。一种解决思路为实现RPC调用，使用C++端（以下称客户端）发送数据，Python端（以下称服务端）处理数据并返回的方法，进一步来说，转换为C++与Python之间通信的问题。2.实现思路因为客户端可能希望使用的函数多种多样，这里为了保证灵活，服务端与客户端均_通过socket实现python和c++数据传输
文章浏览阅读145次。打开.csproject文件把Properties\Resources.Designer.cs相关的东西都删掉，就解决了这个问题了。 <Compile Include="Properties\Resources.Designer.cs"> <AutoGen>True</AutoGen> <DesignTime>True&l..._wpf 加载resx文件