一、二叉树

---

1.1 二叉树按层遍历

1、针对二叉树的宽度优先遍历2、宽度优先遍历常使用队列结构3、面试中，该类题目常对换行有所要示，如将行号也打印出来

题目一：给定一棵二叉树的头节点head，请按照现在大家看到的这种格式打印。要求打印成：

  按层序遍历结果为右侧：

Java 代码实现：

// 层序遍历 // 时间复杂度：O(n) // 空间复杂度：O(n) public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) return res; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> list = new LinkedList<>(); for (int i = 0; i < size; i++) { TreeNode poll = queue.poll(); list.add(poll.val); if (poll.left != null) queue.offer(poll.left); if (poll.right != null) queue.offer(poll.right); } res.add(list); } return res; }

---

1.2 二叉树序列化与反序列化

二叉树     ——>    字符串 （序列化）字符串     ——>    二叉树 （反序列化）

序列化的方式：

根据先序遍历序列化根据中序遍历序列化根据后序遍历序列化按层序列化

案例一：

二叉树被记录成文件的过程叫作二叉树的序列化，通过文件内容重建原来二叉树的过程叫作二叉树的反序列化。给定一棵二叉树的头节点head，并已知二叉树节点值的类型为32位整型。请设计一种二叉树序列化和反序列化的方案，并用代码实现。

案例一答案：

假设序列化结果为str，初始时str为空字符串。先序遍历二叉树时如果遇到空节点，在str末尾加上 “#!”。如果遇到不为空的节点，假设节点值为3，就在str的末尾加上 "3!"。

注意：如果不用特殊符号表示值的结束，则这两棵树的序列化结果为：123###，说明不用特殊字符表示节点值结束的话，会产生歧义。

反序列化：一棵二叉树通过先序遍历得到的结果，如何进行反序列化。

选择用什么样的遍历方式序列化，就选择用什么样的方式反序列化。一棵树序列化的结果是唯一的，唯一的结果生成的二叉树也是唯一的。

---

二、排序

时间复杂度为O(n^2)：冒泡排序、选择排序、插入排序

2.1 冒泡排序

冒泡排序算法思想：

时间复杂度为O(n^2)空间复杂度为O(1)

实现代码：

 

---

2.2 选择排序

选择排序算法思想：

时间复杂度为O(n^2)空间复杂度为O(1)

实现代码：

 

---

2.3 插入排序

插入排序算法思想：

时间复杂度为O(n^2)空间复杂度为O(1)

实现代码：

 

---

时间复杂度：O(N*logN)：归并排序、快速排序、堆排序、希尔排序

2.4 归并排序

归并排序算法思想：

时间复杂度为O(N*logN)空间复杂度为O(1)

实现代码：

 

---

2.5 快速排序

快速排序算法思想：

时间复杂度为O(N*logN)空间复杂度为O(1)

实现代码：

 

---

2.6 堆排序

堆排序算法思想：

时间复杂度为O(N*logN)空间复杂度为O(1)

实现代码：

 

---

2.7 希尔排序

希尔排序算法思想：改进版的插入排序，不断改良步长。希尔排序的关键是步长的选择

时间复杂度为O(N*logN)空间复杂度为O(1)

实现代码：

 

---

时间复杂度为O(N)的排序算法，不是基于比较的排序算法，思想来自于桶排序：计数排序、基数排序

2.8 计数排序

计数排序算法思想：

时间复杂度为O(N*logN)空间复杂度为O(1)

适用场景：数据在一定的范围

实现代码：

 

---

2.9 基数排序

基数排序算法思想：

时间复杂度为O(N*logN)空间复杂度为O(1)

实现代码：

 

---

经典排序算法的空间复杂度

O(1)：插入排序、选择排序、冒泡排序、堆排序、希尔排序O(logN) ~ O(N)：快速排序O(N)： 归并排序O(M)：计数排序、基数排序

---

经典排序算法的稳定性

稳定性的概念：

假定待排序的记序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，称这种排序算法是稳定的，否则称为不稳定的。

稳定的排序概念：

冒泡排序、插入排序、归并排序、计数排序、基数排序、桶排序

不稳定的排序算法：

选择排序、快速排序、希尔排序、堆排序

---

补充说明一：排序算法无绝对优劣

通常不能随便说哪种排序算法好。这个和要排序的元素相关。例如对人的年龄排序或者身高排序，因为这种数据范围通常比较小，可以考虑采用计数排序。但是对于均匀分布的整数，计数排序就不合适了。除非面试题特别说明，否则认为要排序的数据范围是均匀分布的。

补充说明二：为什么叫快速排序

快速排序之所以叫快速排序，并不代表它比堆排序和归并排序优良。在最好的情况下，它的渐进复杂度与 堆排序 和 归并排序 是相同的。只是快速排序的常量系数比较小而已。

补充说明三：工程上的排序

工程上的排序是综合排序。数组较小时，插入排序。数组较大时，快速排序 或 其它 O(N*logN) 的排序。

---

排序案例一：

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离不超过K，并且K相对于数组长度来说很小。请问选择什么方法对其排序比较好。

思路：

时间复杂度为O(N) 的排序算法：计数排序、基数排序，不基于比较排序算法的限制，不适用所有情况。

时间复杂度为O(N^2) 的排序算法：冒泡排序、选择排序。这两个排序算法与数组原始序列无关；插入排序，插入排序的过程与原始顺序有关每个元素移动距离不超过K，对于本题来说，插入排序O(N*K)

时间复杂度为O(N*logN) 的排序算法：快速排序，与数组原始顺序无关。归并排序，与数组原始顺序无关。

答案：改进后的堆排序，数组排序完毕，每得到一个数O(logK)，总共N个数，整体时间复杂度O(N*logK)

---

排序案例二：

判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。

思路：如果没有空间复杂度限制，用哈希表实现。哈希表实现，时间复杂度O(N)，空间复杂度为O(N)。考察经典排序算法，空间复杂度限制。

答案：先排序，排序后相等的值会贴在一起。然后判断。堆排序，需要改写成非递归实现的版本（经典的堆排序是递归）