剑指offer61到66题总览：
- 序列化二叉树
- 二叉搜索树的第k个结点
- 数据流中的中位数
- 滑动窗口的最大值
- 矩阵中的路径
- 机器人的运动范围
61、序列化二叉树
题目描述
请实现两个函数，分别用来序列化和反序列化二叉树
解题思路
序列化指的是遍历二叉树为字符串；所谓反序列化指的是依据字符串重新构造成二叉树。没有说根据什么遍历方法，所以选择前序遍历什么遍历都可以。只要序列化之后再反序列化的树是一样的。
public class Solution {
String Serialize(TreeNode root) {
StringBuffer str = new StringBuffer();
if(root==null){return "#,";}
str.append(root.val+",");//前序遍历树，先根
str.append(Serialize(root.left));//遍历左子树，加到str的后面
str.append(Serialize(root.right));//遍历完左子树，再遍历右子树，加到str的后面
return str.toString();//返回遍历结果
}
int index = 0;
TreeNode Deserialize(String str) {
String[] arr = str.split(",");//如果这个split可以在外面就好一些
TreeNode root = null;//先建一个空结点
if(index < arr.length){
if(arr[index].equals("#")){//如果遇到的是#，则返回空结点
index++;//读了一个结点，index++
return root;//返回空结点
}else{//如果遇到的字符不是#
root = new TreeNode(Integer.valueOf(arr[index]));//new一个新结点，并初始化val的值
index++;//读了一个结点，index++
root.left = Deserialize(str);//先遍历左边的字符
root.right = Deserialize(str);//遍历完左边的字符之后，index会指向相应的右子树的根节点，遍历右边的字符
}
}
return root;
}
}
62、二叉搜索树的第k个结点
题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
解题思路
二叉搜索树中序遍历递增，二叉搜索树中数值第k小的点就是中序遍历的第k个点。
import java.util.Stack;
public class Solution {
int index = 0;
TreeNode KthNode(TreeNode pRoot, int k){
if(pRoot == null){return null;}
if(k<=0){return null;}
Stack<TreeNode> stack = new Stack<>();
stack.push(pRoot);//根节点入栈
while(pRoot.left!=null){//根节点的所有左结点入栈
pRoot = pRoot.left;
stack.push(pRoot);
}
while(!stack.empty()){
TreeNode node = stack.pop();//每出栈一个数，index+1
index++;
if(index < k){//当还没找到第k个数时
if(node.right!=null){如果有右结点，则将右结点入栈，并将右结点的所有左结点入栈
stack.push(node.right);
node = node.right;
while(node.left!=null){//右结点的所有左结点入栈
node = node.left;
stack.push(node);
}
}
}else{//如果找到了第k个数
pRoot = node;//将第k个数赋值给pRoot，并break
break;
}
}
if(stack.empty() && index < k){return null;}//如果是栈空了跳出的循环，且还没到第k个数，则k大于数的总结点数，返回null
return pRoot;//如果是break跳出的循环，则返回pRoot
}
}
63、数据流中的中位数
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解题思路
一个非常直接的思想是，每次插入一个数，都找到新插入的数应该在的位置，使插入的所有数都是有序的，则取中位数的时候很方便。但这种方法的缺点时，在每次插入的时候，都要对之前插入的数据进行遍历。
参考牛客网https://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1的方法，我们设置两个优先队列，也就是两个堆。我们设置一个大顶堆，一个小顶堆。而大顶堆存储插入数据中较小的那一半，小顶堆存储插入数据中较大的那一半。在后续过程中，我们会将大顶堆中的最大元素移出，移到小顶堆中；会将小顶堆中的最小元素移出，移到大顶堆中。所以大顶堆中存的数都比小顶堆中的数小。
为了平衡两个优先队列中的数，插入第一个数的时候，我们可以任意选择先加入小顶堆或者先加入大顶堆中。这个先后顺序只决定了最后我们取中位数的时候，如果我们插入了奇数个数，哪一个优先队列中存的数会多一个，我们就pop出那一个优先队列中存的数，它就是我们要的中位数。如果插入的个数为偶数个，则我们就同时pop出小顶堆和大顶堆中的数，并取平均值，得到中位数。
假设我们约定，当插入数据个数为奇数时，小顶堆的个数要多一个，则整个插入过程如下：(我们设置count，表示已经插入的数据的个数，初始值为0)
- 当count为偶数时，我们将新插入的数先加入大顶堆maxHeap，然后maxHeap再pop出maxHeap中最大的数，将这个最大的数加入到minHeap。这样minHeap就比maxHeap多了一个数。
- 当count为奇数时，minHeap比maxHeap多一个数。我们将新插入的数先加入小顶堆minHeap，然后minHeap再poop出minHeap中最小的数，将这个最小的数加入到maxHeap。这样minHeap和maxHeap的个数就一样了。
这样做，能够保证minHeap中的数总是大于maxHeap中的数，而且我们可以不关心两个堆中数的顺序，只需要关心minHeap中最小的数，和maxHeap中最大的数。同时，minHeap中存的数的个数总是比minHeap中存的数的个数多一个，或者相等。这样就非常方便取中位数了。
取中位数过程如下：
- 当count为偶数时，两个堆的个数是一样的，则取minHeap中最小的数，并取maxHeap中最大的数，取他们的平均值即为中位数。
- 当count为偶数时，minHeap比maxHeap多一个数，只需要取minHeap中最小的数，即为中位数。
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
int count = 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();//小顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b){//大顶堆
return b-a;
}
});
public void Insert(Integer num) {
if(count%2==0){//当插入了偶数个数据的时候
count++;
maxHeap.offer(num);//先将数加入大顶堆
minHeap.offer(maxHeap.poll());//pop出大顶堆中最大的数，并加入小顶堆
}else{
count++;
minHeap.offer(num);//先将数加入小顶堆
maxHeap.offer(minHeap.poll());//pop出小顶堆中最小的数，并加入大顶堆
}
}
public Double GetMedian() {
if(count%2 == 1){//minHeap比maxHeap多一个数，pop出minHeap的顶即可
return (double)minHeap.peek();
}else{//minHeap和maxHeap个数一样，取他们的顶，平均即可
return ((double)minHeap.peek()+(double)maxHeap.peek())/2;
}
}
}
64、滑动窗口的最大值
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
解题思路
参考牛客网https://www.nowcoder.com/questionTerminal/1624bc35a45c42c0bc17d17fa0cba788的方法。我们维护一个双端队列，并存储数组的下标。队头元素下标对应的数是当前滑动窗口中最大的数，队中元素下标对应的数从队头到队尾是递减的。
具体的操作如下：(队列中存储的是对应元素的下标，为了下面表述方便，我们说对应的元素)。
对num数组每个数进行遍历，将num[i]加入到双端队列queue中。
- 如果队列为空，则直接将num[i]对应的下标i加入到queue中，加入到队头队尾都是一样的。
- 如果队列非空，则从队尾开始，逐个向前检查队中下标对应的元素是否小于num[i]，如果小于num[i]，则全部删除，直到遇到比num[i]大的元素即停止。
将队尾中比num[i]小的元素全部删除的原因是，加入了num[i]后，比它小的元素且不说会不会失效，有num[i]在，比num[i]小的元素都不会成为滑动窗口中的最大值，全部删除即可。
另一方面，我们要维护的双端队列是有序的，加入num[i]前，将比num[i]小的元素全部删除，这样才能使队列有序，才能使队头元素成为我们要找的滑动窗口的最大值。 - 要加入i，则滑动窗口向后滑一位，我们要判断队头元素是否过期。如果队头元素对应的下标j<=i-size，即该队头元素已经出了滑动窗口，已经过期，则removeFirst，将队头移出就好。
- 删除了比num[i]小的结点后，并移除了过期队头，然后将num[i]对应的下标i加入到队尾。
- 滑动窗口更新完毕，取队头元素但不remove，加入到list就行。(前size-1个元素不用加入list)
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size){
ArrayList<Integer> list = new ArrayList<>();
if(size <= 0){return list;}
LinkedList<Integer> queue = new LinkedList<>();
for(int i=0; i<num.length; i++){
if(queue.size()==0){//队为空，不用判断是否比num[i]更小，直接加入queue
queue.addFirst(i);//加入下标i
}else{
while(!queue.isEmpty() && num[queue.peekLast()]<num[i]){//从队尾开始，删除队尾中比num[i]小的数
queue.removeLast();
}
if(!queue.isEmpty() && queue.peekFirst() <= i-size){//如果队头元素过期了
queue.removeFirst();//移出队头元素
}
queue.addLast(i);//将新元素加入到队尾
}
if(i >= size-1){//前size-1个元素不用加入list
list.add(num[queue.peekFirst()]);
}
}
return list;
}
}
65、矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
解题思路
递归以及回溯。这个题是可以从matrix中任意一个点开始走的，所以与下一题的机器人路径不一样，这一题的可选方向是上下左右四向，而下一题机器人从(0,0)开始走，可选方向是右和下两向。
判断该方向是否可走，出了判断该点是否出界之外，还要判断该点是否已经存在于已经走过的路径中。一种方法可以将路径保存下来，判断是否存在于已走的路径中。这种方法可以输出可行路径。另一种方法是设置一个visited数组，判断该点是否已经访问过。这种方法能比较快地判断该点是否存在于已经走过的路径中。
如果该点上下左右四向都不通，则该点是错误走法，此时就需要回溯。我们退回走错的前一步，此题的退回即是将visited数组还原为false。
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
if(str.length == 0 || matrix.length == 0){return false;}
boolean visited[] = new boolean[rows*cols];//visited数组标志该位是否被访问
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){//遍历matrix的每一位，从该位开始匹配字符串
if(isHashPath(matrix, str, visited, rows, cols, i, j, 0)){
return true;
}
}
}
return false;
}
public boolean isHashPath(char[] matrix, char[] str, boolean[] visited, int rows, int cols, int i, int j, int str_index){
if(str_index >= str.length){return true;}//str已经全部找到
if(i<0 || i>=rows || j<0 || j>=cols || visited[i*cols+j] || matrix[i*cols+j]!=str[str_index]){
//如果(i,j)点出了边界，或者(i,j)已经被访问，或者(i,j)点对应的字符并不是str_index对应的字符，则返回false
return false;
}
visited[i*cols+j] = true;
//如果没有出边界，也没有被访问，也是str_index对应的字符，则访问该结点，(i,j)点visited设置为true
boolean flag = isHashPath(matrix, str, visited, rows, cols, i, j-1, str_index+1)
|| isHashPath(matrix, str, visited, rows, cols, i, j+1, str_index+1)
|| isHashPath(matrix, str, visited, rows, cols, i-1, j,str_index+1)
|| isHashPath(matrix, str, visited, rows, cols, i+1, j, str_index+1);
//向左，向右，向上，向下递归
if(flag == false){//四向不通
visited[i*cols+j] = false;//四向不通，则说明当前点走错了，回溯，将该点的visited还原为false
}
return flag;
}
}
66 、机器人的运动范围
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
解题思路
这题不用回溯，比上一题相对简单一些。机器人从坐标(0,0)开始走，每次只需要向右和向下走即可，如果向左或向上一定是被访问过的点。每次走的时候，只需要判断向左是否能走，向右是否能走，能走就走，不能走就不走。
public class Solution {
int count = 0;//计数器
public int movingCount(int threshold, int rows, int cols){
if(threshold<=0){return 0;}
boolean visited[][] = new boolean[rows][cols];//是否访问数组
go(threshold, rows, cols, 0, 0, visited);//从坐标(0,0)开始走
return count;
}
public void go(int threshold, int rows, int cols, int i, int j, boolean[][] visited){
if(i<0 || i>=rows || j<0 || j>=cols || visited[i][j]){return;}//如果出了边界或者改点已经访问过，则返回
visited[i][j] = true;//如果没有出边界，且该点没有被访问过，则访问该点，将该点visited设置为true。
count++;//访问该点，计数器count+1
if(canGo(threshold, i, j+1)){go(threshold, rows, cols, i, j+1, visited);}//如果向右走满足threshold，则向右走
if(canGo(threshold, i+1, j)){go(threshold, rows, cols, i+1, j, visited);}//如果向下走满足threshold，则向下走
}
public boolean canGo(int threshold, int i, int j){//判断该点是否满足threshold
int sum = 0;//数位之和
do{
sum += i%10;//先取余，再取商
i = i/10;
}while(i!=0);
do{
sum += j%10;
j = j/10;
}while(j!=0);
if(sum>threshold){return false;}//不满足threshold，返回false
else{return true;}//满足threshold，返回true
}
}
结尾
如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的文章，请点喜欢~*我是蓝白绛，感谢你的阅读！
