题目1 序列化二叉树 题目描述 请实现两个函数，分别用来序列化和反序列化二叉树 题目解析 序列化二叉树可以使用前序遍历来进行，这样的话响应的反序列化在根节点的数值读出来的时候就可以开始了。如果二叉树读的时候遇到NULL，就输出一个“\$ ”。我们以字符串“1,,2,4,$,\$,\$,3,5,\$,\$,6,\$,\$”为例来分析如何反序列化。第一个读出来的数字是1，所以这肯定是根节点的值，接下来读出来的肯定是根节点左子结点上的值，然后接下来再读到的肯定是其左子结点上的值。接着我们读出了两个“$”，这表明4的左右子…

题目4 和为S的两个数字 题目描述 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 题目解析 我们知道，两个数字，距离越远，乘积越小，距离越近乘积越大。所以我们可以设置两个指针，一个指向开头，一个指向末尾，然后他们不断移动，同时相加看是不是等于所制定的值。移动的条件是： 若和大于指定值，则将右指针左移； 若和小于指定值，则将左指针右移； 若到最后左指针和有指针位于一个位置，那么直接返回。 代码 vector<int> Fi…

题目1 二叉树的深度 题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 题目解析 如果一棵树只有一个结点，那么深度为1.如果根节点只有左子树而没有右子树，那么深度就是左子树深度+1；同理，对于右子树也是如此。如果既有左子树，也有右子树，那么该树的深度就是左右子树深度的最大值+1。所以可以利用递归的方式实现该题目。 代码 int TreeDepth(TreeNode* pRoot) { int Hl, Hr, MaxH; if(pRoo…

题目6 第一次只出现一次的字符 题目描述 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。 题目解析 只要这种问题，就可以想到HashTable，但是由于这个问题很简单，而且字符串全部由字母组成，那么每个字母的ASCII码肯定不一样，我们就可以用一个长度为52的数组来记录他们出现的次数，对于字母每出现一次，就对它加1。 当然我们这里为了通用性，可以使用对任意字符进行判断，那么我们就可以考虑实现一个简单的…

题目1 数组中出现次数超过一半的数字 题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 题目解析 最简单的想法就是我们这个数组进行排序，由于数字超过了一半，那么中间的数字（中位数）肯定是我们所需要找的数字。代码实现如代码1所示，但是排序使用快速排序，时间复杂度为O(nlogn)，并没有达到最好的速度。因此参考《剑指offer》一书，我们还可以有两…

题目6 二叉搜索树的后序遍历序列 题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两 个数字都互不相同。 题目解析 我们以后序遍历序列{5,7,6,9,11,10,8}和{7,4,6,5}为例来发现规律。在后序遍历里面，最后一个数字（8,5）一定是序列的根结点值。二叉搜索树左子树都小于根结点的值，右子树都大于根结点的值。 我们先看第一个序列。发现{5,7,6}都小于8，{9,11,10}都大于8，所以前者是左子树，后者是右子树，符合二叉…

题目1 二叉树的镜像 题目描述 操作给定的二叉树，将其变换为源二叉树的镜像。 题目解析 一定要考虑到两种特殊情况： 二叉树为空 二叉树的左子树为空且二叉树的右子树为空 设计代码的时候一定要考虑代码的鲁棒性。所以需要设计到两个if语句，如果不在这两种特殊情况里面，再去新建一个TreeNode，然后交换进行做镜像。 代码 void Mirror(TreeNode *pRoot) { if(pRoot == NULL)//特殊情况1 return; //特殊情况2 if((pRoot->left == NULL)&…