主要是学习剑指offer的一些总结
二叉树的三种遍历：
1、前序遍历：先访问根节点，再访问左子节点，最后访问右子节点。
2、中序遍历：先访问左子节点，再访问根节点，最后访问右子节点。
3、后序遍历：先访问左子节点，再访问右子节，最后访问根节点。
变种遍历：
宽度优先遍历：先访问书的第一层节点，再访问树的第二层节点....一直访问到最下面一层节点。
1、二位数组的查找
2、替换空格
用途：在网络编程中，如果URL参数中含有特殊字符，如空格、“#”等，可能导致服务器无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。
解题思路：
我们可以先遍历一次字符，这样就能统计出字符中空格的总数，并可以由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，可以替换以后字符串的长度等于原来的长度加上2乘于空格数目。我们从字符串的后面开始复制和替换。首先准备两个指针，p1和p2。p1指向原始字符串的末尾，而p2指向替换之后的字符串的末尾。接下来我们向前移动指针p1，逐个把它指向的字符复制到p2指向的位置，直到碰到一个空格为止。
3、从尾到头打印链表
解题思路：
解决这个问题肯定首先要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出，而最后一个遍历到的结点第一个输出。这就是典型的“后进后出”，我们可以使用栈实现这种顺序。每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。
4、用两个栈实现队列
解题思路：
我们通过一个具体的例子来分析往该队列插入和删除的过程。首先插入一个元素啊，不妨先把它插入到stack1，此时stack1中的元素有「a」，stack2空，在一次压入两个元素b和c，还是插入到stack1中，此时stack1中的元素有{a,b,c},其中c位于栈顶，而stack2仍然是空的。
这个时候我们试着从队列中删除一个元素。按照队列先入先出的规则，由于a比b、c先插入到队列中，最先被删除的元素应该是。此时a存储在stack1中，但不在栈顶，而stack2栈为空，所以将stack1依次岀栈到statck2中，在从statck2依次出战。
5、旋转数组中最小的数字
解题思路：
{3,4,5,6,1,2}为{1,2,3,4,5,6}的一个旋转
我们可以注意到旋转之后的数组实际上可以划分为两个排序的子数组，而前面的子数组的元素都大于或者等于后面子数组的元素。我们还注意到最小的元素刚好是这个子数组的分界线。在排序的数组中我们可以用二分法实现O（logn）的查找。
6、二进制中1的个数
7、在0(1)时间删除链表节点
8、反转链表
9、合并排序的链表
解题思路：
链表1的头节点的值小于链表2的头结点的值，因此链表1的头节点是合并后链表的头节点。在剩余的结点中，链表2的头结点的值小于链表1的头节点的值，因此链表2的头节点是剩余结点的头节点，把这个结点和之前已经合并好的链表的尾结点链接起来。
10、数的子结构
解题思路：
第一步在树A中找到和B的根节点的值一样的结点R，第二步再判断树A中以R为根节点的子树是不是包含树B一样的结构。
11、二叉树的镜像
解题思路：
先前序遍历这个树的根节点。
交换根节点的左右子树，如果子树左右子节点不为空，交换左右结点。当交换完所有非叶子节点的左右子结点之后，就得到了树的镜像。
12、顺时针打印矩阵
13、二叉树的后序遍历
14、二叉树中和为某一值的路径
解题思路：
由于路径是从根节点出发到叶结点，也就是路径总是以根节点为起始点，因此我们首先需要遍历根节点。所以选择前序遍历。
15、字符串的排列
解题思路：
我们求整个字符串的排列，可以看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。这个时候我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。
16、第一次值出现一次的字符
解题思路：
我们先可以统计每个字符在该字符串中出现的次数，要达到这个目的，我们需要一个数据容器来存放每个字符的出现的次数。在这个数据容器中我们可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中，哈希表正是这个用途。
为了解决这个问题，我们可以定义哈希表的键值是字符，而值是该字符出现的次数。同时我们还需要从头开始扫描字符串两次。第一次扫描，记录每个字符出现的次数，第二次扫描，根据值1的次数就是需要打印的字符。
17、删除链表中重复的点
解题思路：
我们从头遍历整个链表，如果当前结点的值与下一个结点的值相同，那么他们就是重复的结点，都可以被删除，为了保证删除之后的链表仍然是相连的而没有中间断开，我们要把当前结点的前一个结点和后面值比当前结点的值要大的结点相连。
18、对称的二叉树
解题思路：
可以通过变种的对称前序遍历来判断二叉树是不是对称的。通过递归。
19、把二叉树打印多行
解题思路：
我们可以用一个队列来保存将要打印的结点，为了把二叉树的每一行单独打印到一行里，我们需要两个变量：一个变量表示在当前层还没有打印的结点数，另一个变量表示下一层节点的数目。
20、按之字形打印二叉树
21、句子的逆序问题
网友评论