基础算法介绍
时间复杂度分析
算法思想
贪心算法
分治
动态规划
回溯法
枚举法
元算法
排序算法
排序算法是一种元算法。
O(N^2)
- 插入排序
- 选择排序
- 希尔排序
- 冒泡排序
O(nlogn)
- 快排
- 归并排序
- 堆排序
O(n)
- 桶排序
- 计数排序
- 基数排序
查找算法
- 线性查找
- 树查找
- 散列表查找
二叉树的遍历算法
概述
二叉树作为一个基础的数据结构，遍历算法作为一个基础的算法，两者结合当然是经典的组合了。有直接问二叉树的遍历的，有间接问的。比如要你找到书中满足条件的节点，就是间接考察树的遍历，因为你要找到书中满足条件的点，就需要遍历。
如果掌握了二叉树的遍历，那么其他复杂的树相对于你来说，也并不遥远了。
二叉树的遍历主要有前中后遍历和层次遍历。前中后属于DFS，层次遍历属于BFS。 DFS都可以用栈来简化操作。并且其实树本身就是一种递归的数据结构，因此递归和栈对于DFS来说是两个关键点。
前序遍历
前序遍历的顺序是 根-左-右
思路是：
- 先将根节点入栈
- 出栈一个元素，将右节点和左节点以此入栈
- 重复2的步骤
总结：典型的递归数据结构，典型的用栈来简化操作的算法。
中序遍历
中序遍历的顺序是 左-根-右，根节点不是先输出，这就有点复杂了。
- 根节点入栈
- 判断有没有左节点，有则入栈，直到叶子节点
此时栈中保存的就是所有的左节点和根节点。
- 出栈，判断有没有右节点，有则入栈，继续执行2
值得注意的是，中序遍历是一个二叉查找树（BST）的结果是一个有序数组，利用这个性质有些题目可以得到简化。
后序遍历
后序遍历的顺序是 左-右-根
这个有点难。
其实这个也是属于根节点先不输出，并且根节点是最后输出。这里可以采用一种很讨巧的做法，就是记录当前节点状态，如果
- 当前节点是叶子节点或者
- 当前节点的左右子树都已经遍历过了，那么就可以出栈了
对于1，这个比较好判断，只要判断left和right是否同时为null就好。 对于2，当前节点的左右子树都已经遍历过了，我们只需要用一个变量记录即可。最坏的情况，我们记录每一个节点的访问状况就好了，空间复杂度O（n）。但是细想一下，我们使用了栈的结构，从叶子节点开始输出，我们记录一个当前出栈的元素就好了，空间复杂度O（1）。
层次遍历
层次遍历的关键点在于如何记录每一层次是否遍历完成，我们可以用一个标志位来表示当前层的结束。 具体做法：
- 根节点入队列，并入队列一个特殊的标志位，此处是null
- 出队列
- 判断是不是null，如果是则代表本层已经结束。我们再次判断是否当前队列为空，如果不为空继续入队一个null，否则说明遍历已经完成，我们什么也不用做
- 如果不为null，说明这一层还没完，则将其左右子树以此入队列
递归和动态规划
动态规划可以理解为是查表的递归。那么什么是递归？
递归
定义：递归算法是一种直接或者间接调用自身函数或者方法的算法。 算法中使用递归可以很简单的完成一些用循环实现的功能，比如二叉树的左中右序遍历。递归在算法中有非常广泛的使用。
纯粹的函数式编程中没有循环，只有递归
通俗来说，递归算法的实质就是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解
递归三要素
- 一个问题的解可以分解为几个子问题的解
- 子问题的求解思路除了规模之外，没有任何区别
- 有递归终止条件
列举几道算法题目，可以用递归很轻松的写出来：
- 递归实现sum
- 二叉树的遍历
- 走楼梯问题
- 汉诺塔问题
- 杨辉三角
练习递归
一个简单练习递归的方式是将你写的迭代全部改成递归形式。比如你写一个程序，功能是“将一个字符串逆序输出”，那么用迭代将其写出来会非常容易，那么递归呢？通过这样，可以让你逐步适应使用递归来写程序。
递归中的重复计算
递归中存在这么多的重复计算，一种简单的方式就是记忆化递归。即一边递归一边使用“记录表”记录我们已经计算过的情况，这样就避免了重复计算。而动态规划中DP数组其实就和“记录表”一样。
动态规划
如果说递归是从问题的结果倒推，直到问题的规模缩小到寻常。那么动态规划就是从寻常入手，逐步扩大规模到最优子结构。
动态规划的两个要素
- 状态转移方程
- 临界条件
动态规划为什么要画表格
动态规划问题要画表格。
其实动态规划本质上是将大问题转化为小问题，然后大问题的解和小问题有关联的，换句话说大问题可以由小问题进行计算得到。这一点和递归是一样的，但是动态规划是一种类似查表的方法来缩短时间复杂度和空间复杂度。
画表格的目的就是不断推导，完成状态转移，表格中的每一个cell都是一个小问题，我们填表的过程其实就是在解决问题的过程，我们先解决规模为寻常的情况，然后根据这个结果逐步推导，通常情况下，表格的右下角是问题的最大的规模，也就是我们想要求解的规模。
总结
请记住：
递归是从问题的结果倒推，直到问题的规模缩小到寻常。动态规划是从寻常入手，逐步扩大规模到最优子结构。