1245. Tree Diameter

解题思路：本题是一道图上做有记忆的dfs搜索的题目，是无向图，给定的输入是图的各个边，题目中给出一个关键信息(Each node has labels in the set {0, 1, …, edges.length})可知图中没有环，如果是有环的图这个题是无解的。最好的证明方法就是反正法，如果有环的话标号最大的节点必然小于边的数量，例如[0, 1], [1, 2], [0, 2], 三个节点且三条边，但编号最大的节点小于边的数量。 作为一个无向不联通图，节点主要分为两种类型，一种可以称为叶节点(这个并非是官方的名字，只是我自己叫着方便)，即只有一个边与它连接，除来叶节点之外的节点则至少有两个边相连。 题目要求找出最长的一个path依次来定义这个tree的直径，很显然直径的选择是从一个叶节点到另外一个叶节点，在构建完图之后找到所有的叶节点，开始进行dfs的遍历，找出其中最长的一条路径来定义树的直径。 这个题目的模型与 568. Maximum Vacation Days 最大的不同是在计算过的值的记忆部分。 在568中每个节点的进与出的部分很清晰的分离，因此只要计算过一次，下一次递归不团从哪个节点进，都返回同样的答案。 本题则需要根据不同的输入返回不同的结果，所以memo的数据结构也不一样，对于每一个节点，需要用一个map来对应该节点到下一个节点的答案。这个地方需要使用map，而不是vector，因为需要使用到下一个节点的序号来索引。如果选择vector，无法将序号转换成下表。 时间复杂度：对于每一个节点而言，图需要计算各个出的值，复杂度为 O(e) 空间复杂度：存储每个节点到每一个方向的值 O(e)

568. Maximum Vacation Days

解题思路：这是一道在图上做有记忆dfs的题目，图的信息通过矩阵给出。一共有N个城市，城市之间的连同关系在 flights 矩阵中，代表着dfs中下一次递归的可行选择。另外一个给出的信息是K个星期中在每一个城市可以得到的假期数量，题目要求找出K个星期中最多的假期，这也是每次递归中需要累加的值，K也是递归终止的条件。 为了节省时间复杂度，需要另外分配一个memo的矩阵将之前计算过的值保留，如果这个值不为 0 每次递归直接返回。 注意：给出的航班信息表中没有每个城市到自己的航班，即flight[i][i] 为0 ，这个符合常识，但并不符合题意。因为两个星期之间并不一定非要飞到另外一个城市，如果呆在本地假期更多也可以不飞，需要做一个预先的处理就是将 flights[i][i] 全部置为1。 时间复杂度：这个取决于矩阵的稀疏程度，也就是到下一个城市可以的选择，这个有由flights 矩阵给出，假设每两个城市之间都有相互连接的航班，共需要做K次的选择，每次计算后将结果保存避免不必要的时间消耗，最终的复杂度为 O(N * K) 空间复杂度：为每个城市在每个星期分配一个变量保存计算过的值，复杂度 O(N * K)