[LeetCode]Minimum Height Trees

一道需要我们事先做一些分析的题目，一个图中可能有多少这样的节点，可以使以其为根节点的时候深度最小。事实上，这样的节点只可能在最长的路径上，并且一定是最中间的一个或者两个节点。假设tree中最长的路径p长度为d，那么我们取中点为root的时候整个tree的最大的深度就是d/2, 因为假设有其他的点c深度超过d/2，那么把p的一半和root再与c相连，整个长度肯定是大于d的，这和我们的假设矛盾。假设有其他不在p上的点n可以在其当root的时候使整个tree的深度小于d/2，那么既然n不在p上，那么因为从p的两头到点n肯定分别只有一条路径（否则会有环），并且共同经过p上的某个节点，那么p的两个端节点，深度是不可能小于d/2的，我们得到了矛盾的结论。所以假设成立，那么找tree中最长的路径，我们可以用DFS或者BFS，DFS的话，我们从任意节点开始，找到某个叶节点，然后从叶节点DFS找到最长路径，然后去其中点即可，假设我们总共有N个节点，那么有N-1条边（N个节点connected至少需要N-1条边，大于N-1条边会产生环），建图和DFS都是O(N)，所以总的时间复杂度就是O(N),代码如下：

BFS的话，我们就类似剥洋葱，从外部的叶节点开始向里面一层一层的删除，知道最后剩下的一个或者两个节点，就是最长路径上的中点，时间复杂度O(N), 代码如下：