本题给你一个无向图,其中有n个顶点,n-1条边,因此取其中的任意某顶点作为根,都可以构建成一棵树。那么本题的问题就是在这些树中找出高度最小的树,返回树的根节点;如果有多棵树的高度相同,则返回多个根节点。
思路1:一开始,我认为最直白的解法就是遍历所有的顶点,以该顶点为根,求此树的高度。最后找出高度最小的树就是答案。此为暴力法,但是暴力一般往往会超时,本题也不例外。所以就得另辟蹊径咯。
思路2:先找到所有的叶子节点(该顶点只与一个顶点连接,即只有一条边),再删除所有的叶子节点,再继续找目前的叶子节点,再删除掉。直到找不到叶子节点为止。那么最后一次找到的叶子节点就是所求的根节点。这题算是trick吧,自己多画几个图,或许可以发现这个规律。
好了,代码如下。