P161. 高度最小的树

leetcode 310 lintcode 1298 BFS DFS 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,给你一个没有环的无向图,把图上任意一个节点当作根节点,就可以把它看作一棵树。这样一来,对于一个包含 n 个节点的无环无向图,可以产生 n 棵不同的树。你要找出这 n 棵树中,所有高度最小的树,并返回它们的根节点。其中,高度的定义是:根节点和最远的叶子节点之间,边的数量。

注意,给你的 n 是一个正整数,表示图上共有 n 个节点,编号从 0 到 n-1。另外给你一组数字对,表示连接两个节点的边。并且给你的这组数字对中,不包含重复的边。

比如说,给你的 n 等于 4,给你的表示边的数字对是:

[0, 1],
[0, 2],
[0, 3]

它表示这样一个无向图:

  1
  |
  0
 / \
2   3

在这个无向图中,高度最小的树只有一棵,就是以 0 为根节点的树。于是返回:[0]。

如果把 n 改成 5,然后再加一条边 [3, 4],这个无向图就会变成:

  1
  |
  0
 / \
2   3
    |
    4

在这个无向图中,高度最小的树有两棵(高度为 2),返回它们对应的根节点是:[0, 3]。

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。