1043 Is It a Binary Search Tree
1. 这是二叉查找树BST那节的习题，要做出来这题，需要具备的基础知识有：BST的创建，涉及函数createBST，insertBST，newNode，二叉树的先序遍历、后序遍历。
2. 需要转过来的弯的有：
给定了序列，其实就可以创建出唯一的BST了。也就是一开始给定的那个序列，不要管他是什么序，反正就是个确定的序列。后面用来比对的时候再看他是不是先序，是不是镜像先序。
所谓镜像就是把检索左右子树的位置互换以下。
3. 一个非常使用的技巧：向量容器盛整数可以直接比对序列。详见妙用vector:根据第一个不等的元素比较两个序列大小的利器
4. 我犯了一个非常傻的错误，在遍历的时候第一句应该是root==NULL退出，写成了!=，导致我一直在纠结传进来的参数的引用写的对不对。也调试不出，后来猛然看见的。
AC代码
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long LL;using namespace std;const int maxn = 100010;struct Node{int data;Node *lchild,*rchild;
};Node* newNode(int v){Node* node = new Node;//申请变量的地址空间node->lchild = node->rchild = NULL;//新建的结点没有左右孩子node->data = v;//数据域为传进的参数值return node;
}void insertBST(Node* &root,int v){//由于要对二叉树的结构进行修改，所以传入根节点的引用if(root==NULL){//查找失败的位置，就是要插入的位置root = newNode(v);return;}if(v<root->data)insertBST(root->lchild,v);//根据BST的性质，此时往左子树搜索 else insertBST(root->rchild,v);
}Node* createBST(vector<int> data,int n){//data是待插入值域的数组，n是数组长度 Node* root = NULL;for(int i=0;i<n;i++){insertBST(root,data[i]);}return root;
}void preOrder(Node* root,vector<int>& preSeq){if(root==NULL)return;preSeq.push_back(root->data);preOrder(root->lchild,preSeq);preOrder(root->rchild,preSeq);
}void mirrorPreOrder(Node* root,vector<int>& mirrorPreSeq){if(root==NULL)return;mirrorPreSeq.push_back(root->data);mirrorPreOrder(root->rchild,mirrorPreSeq);mirrorPreOrder(root->lchild,mirrorPreSeq);}void postOrder(Node* root,vector<int>& postSeq){if(root==NULL)return;postOrder(root->lchild,postSeq);postOrder(root->rchild,postSeq);postSeq.push_back(root->data);
}void mirrorPostOrder(Node* root,vector<int>& mirrorPostSeq){if(root==NULL)return;mirrorPostOrder(root->rchild,mirrorPostSeq);mirrorPostOrder(root->lchild,mirrorPostSeq);mirrorPostSeq.push_back(root->data);
} int main(){int n,data;vector<int> initSeq,preSeq,mirrorPreSeq,postSeq,mirrorPostSeq;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&data);initSeq.push_back(data);}Node* root = createBST(initSeq,n);preOrder(root,preSeq);if(preSeq==initSeq){printf("YES\n");postOrder(root,postSeq);for(int i=0;i<postSeq.size();i++){printf("%d",postSeq[i]);if(i!=postSeq.size()-1)printf(" ");}return 0;}mirrorPreOrder(root,mirrorPreSeq);if(mirrorPreSeq==initSeq){printf("YES\n");mirrorPostOrder(root,mirrorPostSeq);for(int i=0;i<mirrorPostSeq.size();i++){printf("%d",mirrorPostSeq[i]);if(i!=mirrorPostSeq.size()-1)printf(" ");}return 0;}printf("NO"); return 0;
}邪门，第二次做代码优化了，对于镜像居然检测不出
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
#include<stdlib.h>
#include<time.h>
#include<vector>
#include<set>
#include<string>
#include<tr1/unordered_map>using namespace std;
using namespace std::tr1;
typedef long long LL;const int maxn = 107;
const int MOD = 1000000007;
const int INF = 1000000000;//INF:下确界
const LL SUP = (1LL<<63)-1;//SUP:上确界
const double eps = 1e-5;struct Node{int v;Node *lchild,*rchild;
};void insert(int x,Node* &root){if(root==NULL){root = new Node;root->v = x;root->lchild = root->rchild = NULL;return;}if(x<root->v)insert(x,root->lchild);else insert(x,root->rchild);
}vector<int> initV,testV,testV2,postV;void preOrder(Node* root){if(root==NULL)return;testV.push_back(root->v);if(root->lchild!=NULL)preOrder(root->lchild);if(root->rchild!=NULL)preOrder(root->rchild);
}void preOrderMir(Node* root){if(root==NULL)return;testV2.push_back(root->v);if(root->rchild!=NULL)preOrder(root->rchild);if(root->lchild!=NULL)preOrder(root->lchild);
}void postOrder(Node* root){if(root==NULL)return;if(root->lchild!=NULL)postOrder(root->lchild);if(root->rchild!=NULL)postOrder(root->rchild);postV.push_back(root->v);
}void postOrderMir(Node* root){if(root==NULL)return;if(root->rchild!=NULL)postOrder(root->rchild);if(root->lchild!=NULL)postOrder(root->lchild);postV.push_back(root->v);
}int main(){int n,x;cin>>n;for(int i=0;i<n;i++){cin>>x;initV.push_back(x);}Node* root = NULL;for(int i=0;i<n;i++){insert(initV[i],root);}preOrder(root);if(testV==initV){printf("YES\n");postOrder(root);for(int i=0;i<postV.size();i++){printf("%d%s",postV[i],i==postV.size()-1?"\n":" ");}return 0;}preOrderMir(root);if(testV2==initV){printf("YES\n");postV.clear();postOrderMir(root);for(int i=0;i<postV.size();i++){printf("%d%s",postV[i],i==postV.size()-1?"\n":" ");}return 0;}printf("NO\n");return 0;
}相关文章：
运用比较纯的CSS打造很Web2.0的按钮
警告：如果你在使用IE浏览此文，那么请回避一下吧! 什么，你用的还是IE6？你真奥特曼(推荐你去打小怪兽)！ 先上图，所谓有图有真相。 如果您觉得图片上这些按钮不够2.0，那没办法，请回避吧…
Elasticsearch 参考指南（脚本）
脚本 脚本模块使你可以使用脚本来评估自定义表达式，例如，你可以使用脚本将“脚本字段”作为搜索请求的一部分返回，或者为查询评估自定义分数。 默认脚本语言是Painless，附加的lang插件使你可以运行用其他语言编写的脚本࿰…
eclipse如何卸载adt插件
1、选择 Help Install New Software； 2、在Details 面板中, 点击What is already installed? 链接； 3、在Eclipse Installation Details 对话框中，选择Android DDMS和Android Development Tools ，然后点击Uninstall；…
1099 Build A Binary Search Tree
1. 本题给出了树的样子，给出了用来填充的数列，并且告诉是一棵二叉查找树。 2. 先用静态存储的方式将树的框架建立起。然后对数列进行小到大排序，利用BST中序遍历是升序的性质，通过中序遍历将数值填充的树中。 3. 层序输出的时候…
redis4.0.6集群部署（5.0.2版本更新补充）
Redis集群安装4版本需要ruby 5版本不需要ruby就能集群1集群机器分布192.168.1.133 redis1192.168.1.134 redis2192.168.1.135 redis32 免密登录ssh-keygenssh-copy-id 192.168.1.133ssh-copy-id 192.168.1.134ssh-copy-id 192.168.1.1353 关闭防火墙sy…
PHP多图片上传 并检查 加水印 源码
参数说明:$max_file_size : 上传文件大小限制, 单位BYTE$destination_folder : 上传文件路径$watermark : 是否附加水印(1为加水印,其他为不加水印);使用说明:1. 将PHP.INI文件里面的"extensionphp_gd2.dll"一行前面的;号去掉,因为我们要用到GD库;2. 将extension_dir…
C#中的委托和事件 (4)---事件和委托的编译代码
事件和委托的编译代码 这时候，我们不得不注释掉编译错误的行，然后重新进行编译，再借助Reflactor来对 event的声明语句做一探究，看看为什么会发生这样的错误： public event GreetingDelegate MakeGreet; 可以看到&#…
1066 Root of AVL Tree 需再做
1. 这题如果不知道平衡二叉树怎么平衡的(左旋右旋那一套)应该不可能做出吧，那就输出中位数回点血了。 2. 需要具备的基础知识：怎么将结点插入平衡二叉树。 3. 我犯的一个错误：把更新高度的函数直接返回了高度，而不没有修改高度。…
easyui-menu 解决disableItem不能禁用绑定事件的方法
版本：1.4. menu的disableItem方法不能禁用使用onClick方式绑定的事件。 解决思路如下： 重写disableItem方法和enableItem方法。 /*** menu方法扩展* param {Object} jq* param {Object} itemEl*/ $.extend($.fn.menu.methods, {/*** 激活选项࿰…
hadoop无法访问50070端口怎么办？
转载请注明出处：www.oldboyedu.com Hadoop 50070是hdfs的web管理页面，在搭建Hadoop集群环境时，有些大数据开发技术人员会遇到Hadoop 50070端口打不开的情况，引起该问题的原因很多，想要解决这个问题需要从以下方面进行排…
表情的机器自动识别(有图有真相)
这幅图片是我自己用C#编写的表情的机器自动识别。主要是AdaBoost的实现，训练做了几个不同版本：线性、并行和分布式，训练数据集采用的JAFFE。 有朋友问这东西有什么用处，其实主要是为了玩而已了。这是基于Paul Ekman那本著名的《情…
并查集专题练习：好朋友(未完待续)
有空再把题目补上 输入样例1 4 2 1 4 2 3 样例输出1 2 输入样例2 7 5 1 2 2 3 3 1 1 4 5 6 输出样例2 3 解题思路： 1. 这题放在并查集的专题后面，有查找也有合并，需要具备的基础只是是合并和查找的函数要会写(都很简单)。但是读到每…
android Viewpager取消预加载及Fragment方法的学习
1.在使用ViewPager嵌套Fragment的时候，由于VIewPager的几个Adapter的设置来说，都会有一定的预加载。通过设置setOffscreenPageLimit（int number) 来设置预加载的熟练，在V4包中，默认的预加载是1，即使你设置为…
前端Js框架 UI框架汇总 特性 适用范围 选择
身为一个资深后端工程师，面对层出不穷的前端框架，总让人眼花缭乱，做一个综合解析贴，从全局着眼，让我们明白各种前端框架的应用范围，为如何选择前端框架，从不同的维度提供一些线索，做…
Emptyproject分析
Emptyproject分析(SimpleSample)1，InitApp()WinMain中有一个InitApp()，在sample中存在，但是在emptyproject中没有，该函数是用于设定已经声明的一些一般变量的初始值的。比如某些按钮。2，IsDeviceAcceptable()被WinMain…
1107 Social Clusters
这道题目给出的示例如上图所示，一共有1-8这8个人(圆形)，他们拥有1-10这10个兴趣爱好(方形)，一人可以有多个爱好，拥有共同爱好的人被视为一个社区的。现在给出每个人的爱好情况，求出社区的个数，并按照从大到…
c#直接调用ssis包实现Sql Server的数据导入功能
调用ssis包实现Sql Server的数据导入功能网上已经有很多人讨论过，自己参考后也动手实现了一下，上一次笔者的项目中还用了一下这个功能。思前想后，决定还是贴一下增强记忆，高手请54.1、直接调用ssis包，需要引用Microsof…
从入门到放弃的javaScrip——队列
队列数据结构 队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。 现实中，很常见的例子就是…
css控制不换行
white-space:nowrap; 转载于:https://www.cnblogs.com/w8104254/p/4178198.html
(C++)堆排序的3个关键函数
堆排序：指使用堆结构对一个序列进行排序。所以，首先要有一个堆结构。 此处讨论递增排序。以及用最大堆。 注意：让存放堆的数组作为全局变量，n为元素个数，数组存放元素从下标1开始，n结束。 int heap[11] …
android 横竖屏限制如何配置
在开发android的应用中，有时候需要限制横竖屏切换。只需要在AndroidManifest.xml文件中加入android:screenOrientation属性限制。 ndroid:screenOrientation"landscape"是限制此页面横屏显示， ndroid:screenOrientation"portrait"是…
Java面试题总结-Day4
<?xml version"1.0" encoding"utf-8"?> Java面试题总结-Day4Java面试题总结-Day4 Table of Contents 1. ArrayList和LinkedList区别 1.1. 是否线程安全1.2. 底层数据结构1.3. 插入和删除是否受元素位置的影响1.4. 是否支持快速随机访问1.5. 内存空…
Linux 使用者身份與群組記錄的檔案
在我們Linux系統當中，預設的情況下，所有的系統上的帳號與一般身份使用者，還有那個root的相關資訊， 都是記錄在/etc/passwd這個檔案內的。至於個人的密碼則是記錄在/etc/shadow這個檔案下。 此外，Linux所有的群組名稱都…
1098 Insertion or Heap Sort 需再做
1. 应该还做过一道类似的题目，也是要求判断属于哪种排序的中间过程，并要求写出下一轮排序结果，这次的进步是上来就知道用向量存数据，这样方便直接比较，而且下标0不能存元素，因为堆排序的堆是一个完全二叉树…
基于node.js的压缩合并安装
1.构建工具（grunt,gulp） 下载地址：http://gruntjs.cn/http://gruntjs.com/（1）安装nodejs(http://www.nodejs.org/) 验证是否安装成功，命令行输入 node -v （2）grunt 的安装 安装全局…
jenkins 修改工作目录
修改Jenkins路径 Jenkins的默认安装路径是/var/lib/jenkins 现在由于这个根目录的磁盘太小，所以切换到/data 目录下。 Jenkins目录、端口、工作目录等信息在/etc/sysconfig/jenkins 下，所以需要修改这个文件。 将JENKINS_HOME"/var/lib/jenkins&quo…
破一个行业ERP的感想
今天闲来无事，找来破一破。 这个是一个行业性质的ERP软件，有授权码验证，客户机数量限定，以及使用时间限定，被一一破解。 授权码存在明显的绕过bug.客户机数量同样被明文标注在文件中。使用时间也是标注在文件中&#x…
1034 Head of a Gang(图的DFS解法) 擦边大法好
1.题目的大意是给出很多人(结点)之间的通话记录，每两人之间的权重取决于他俩通话权重的总时长，如果一个社区的人数超过2且社区内发生的通话总时长超过给定阈值，那么这属于一个社区。最后要求输出社区的总数，再按照社区头目的姓名字…
Android定位方式和测试方法
Android常用的三种定位方式有：基于GPS定位、基于基站地位、基于wifi定位。 1、基于GPS定位： GPS定位需要GPS模块(硬件)的支持,没有GPS模块是无法进行GPS定位的。 GPS定位最大的优点就是其定位精确度高(一般误差在10m内),无网络也能用;缺点就是耗电高、定…
vue el-form鼠标事件导致页面刷新解决方案；vue 阻止多次点击提交数据通用方法...
一.阻止表单自动提交刷新页面：<el-form><el-form-item :inline"true" submit.native.prevent><el-input keyup.enter.nativesubmit></el-input></el-form-item> </el-form>注意： 鼠标事件导致页面刷新问…