1）假设以X节点为头，假设可以向X左子树和X右子树要任何信息
2）在 1) 的假设下，讨论以X为头节点的数，得到答案的可能性
3）列出所有可能性后，确定到底需要向左子树和右子树要什么样的信息
4）把左子树信息和右子树信息求全集，就是任何一颗子树都需要返回的信息S
5）递归函数都返回S，每一颗子树都这么要求
6）在代码中考虑如何把左子树的信息和右子树的信息整合出整棵树的信息

1、给定一颗二叉树的头节点head，返回这颗二叉树是不是平衡二叉树

2、给定一颗二叉树的头节点head，任何两个节点之间都存在距离，返回整颗二叉树的最大距离

3、给定一颗二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树

4、派对的最大快乐值问题

每个员工都符合Employee类的描述，整个公司的人员结构可以看做是一颗标准的、没有环的多叉树。树的头节点是公司唯一的老板，除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工(nexts列表为空)，除基层员工外，每个员工都有一个或多个直接下级。
现在这个公司要举办一个Party，你可以决定哪些员工来，哪些员工不来，规则：
1、如果某个员工来了，那么这个员工的所有直接下级都不能来；
2、Party的整体快乐值是所有到场员工快乐值的累加；
3、你的目标是让Party的整体快乐值尽量大。
给定一棵树多叉树的头节点Boss，请返回Party的最大快乐值。

5、给定一颗二叉树的头节点，返回这颗二叉树是不是满二叉树

6、给定一颗二叉树的头节点，返回这颗二叉树是不是完全二叉树

7、给定一颗二叉树的头节点，和另外两个节点a和b，返回a和b的最低公共祖先

8、贪心算法

1）最自然智慧的算法
2）用一种局部最功利的标准，总是做出在当前看来是最好的选择
3）难点在于证明局部最功利的标准可以得到全局最优解
4）对于贪心算法的学习主要以增加阅历和经验为主

给定一个由字符串组成的数组strs，必须把所有的字符串拼起来，返回所有可能的拼接结果中，字典序最小的结果

9、贪心算法的套路

1）实现一个不依靠贪心策略的解法X，可以尝试暴力穷举
2）脑补贪心策略A，贪心策略B，贪心策略C…
3）用解法X和对数器，加上实验的方式得知哪个贪心策略是正确的
4）不纠结贪心策略的证明，累不死你

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给定每一个项目开始的时间和结束的时间，请安排宣讲的日程，要求会议室进行的宣讲的场次最多，返回最多的宣讲场次

暴力穷举：

贪心策略：

给定一个字符串str，只由’X’和’.’两种字符构成：
‘X’表示墙，不能放灯，也不需要点亮；
‘.’表示居民点，可以放灯，需要点亮。
如果灯放在i位置，可以让i-1、i和i+1三个位置被点亮，返回如果点亮str中所有需要点亮的位置，至少需要几盏灯

暴力穷举：

贪心策略：

一块金条切成两半，是需要花费和长度数值一样的铜板。比如长度为20的金条，不管怎么切，都要花费20个铜板。一群人想分整块金条，怎么分最省铜板？
例如：给定数组{10,20,30}代表一共3个人，整块金条长度为60，金条要分成10,20,30三个部分。
如果要把长度60的金条分成10和50，花费60；再把长度为50的金条分为20和30，花费50；一共花费110铜板；
如果要把长度60的金条分成30和30，花费30；再把长度为30的金条分为10和20，花费20；一共花费90铜板；
输入一个数组，返回分割的最小代价

暴力穷举：

贪心策略：

输入：正数数组costs、正数数组profits、正数K、正数M
costs[i]表示i号项目的花费
profits[i]表示i号项目在扣除花费之后还能挣到的利润
K表示只能串行的最多做K个项目
M表示初始的资金
说明：每做完一个项目，马上获得的收益，可以支持去做下一个项目（不能并行做项目）
输出：最后获得的最大钱数

10、并查集

1）有若干个样本a、b、c、d…类型假设是V
2）在并查集中一开始认为每个样本都在单独的集合里
3）用户可以再任何时候调用如下两个方法：
boolean isSameSet(V x, V y)：查询样本x和样本y是否属于一个集合
void union(V x, V y)：把x和y各自所在集合的所有样本合并成一个集合
4）isSameSet和union方法的代价越低越好

如果两个User中，a一样或b一样或c一样，则认为是一个User。请合并User，返回合并之后的用户数量

11、图

1）由点的集合和边的集合构成
2）虽然存在有向图和无向图的概念，但实际上都可用有向图来表示
3）边上可能带有权值
4）图的算法并不难，但是编码的代价一般都比较高，在编码的时候优先选择自己最熟悉的结构

图结构

将矩阵转为图结构

图的宽度优先遍历

图的深度优先遍历

图的拓扑排序算法
1）在图中找到所有入度为0的点输出
2）把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始
3）图的所有点都被删除后，一次输出的顺序就是拓扑排序
要求：有向图且其中没有环
应用：事件安排、编译顺序

最小生成树算法之Kruskal
1）总是从权值最小的边开始考虑，依次考察权值依次变大的边
2）当前的边要么进入最小生成树的集合，要么丢弃
3）如果当前的边进入最小生成树的集合中不会形成环，就要当前边
4）如果当前的边进入最小生成树的集合中会形成换，就不要当前边
5）遍历完所有边之后就可以得到最小生成树的集合

最小生成树算法之Prim
1）可以从任意节点出发来寻找最小生成树
2）某个点加入到被选取的点中后，解锁这个点出发的所有新的边
3）在所有解锁的边中选最小的边，然后看看这个边会不会形成环
4）如果会，不要当前边，继续考虑剩下解锁边中最小的边，重复3）
5）如果不会，要当前边，将该边指向点加入到被选取的点中，重复2）
6）当所有点都被选取，就得到了最小生成树

Dijkstra算法
1）Dijkstra算法必须指定一个源点
2）生成一个源点到各个点的最小距离表，一开始只有一条记录，
即源点到自己的最小距离为0，源点到其它所有点的最小距离都正无穷大
3）从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，
更新源点到各个点的最小距离表，不断想重复这一步
4）源点到所有的点记录如果都被拿过一遍，过程停止，也就生成了最小距离表