给定具有根节点和特定节点的二叉树（不一定是二叉搜索树），如何找到离给定节点最近的叶节点？
是否有针对此问题的特定算法或现有算法的修改？
问问题
3231 次
3 回答
2
检查此链接。这个想法是按顺序遍历给定的树并跟踪数组中的祖先。当我们到达给定键时，我们评估以给定键为根的子树中最近叶子的距离。我们还一一遍历所有祖先，并找到以祖先为根的子树中最近的叶子的距离。我们比较所有距离并返回最小值。
于 2015-01-18T02:11:59.940 回答
2
这是一个非常典型的图遍历问题。您可以使用Dijkstra 算法遍历图形并找到到达目的地的最短路径。
在这种情况下，我们使用 Dijkstra 而不是 A*，因为我们不知道我们的目的地是什么。如果你玩过星际争霸，这（几乎可以肯定）是工人用来寻找最近的矿物供应或需要维修的最近车辆的工具。
于 2013-06-18T19:03:52.373 回答
0
如果一个节点保持到其父节点的反向链接的假设是正确的，那么执行 BFS 就足够了。这个想法是首先到达感兴趣的节点，然后对其子节点及其父链接进行 BFS（然后每个父链接将对其子节点执行 BFS，不包括您已经访问过的节点及其父节点）。您保持从感兴趣节点到叶子的最小距离 (MinDistance)，并且不要在距离 >= MinDistance 的非叶子节点上进行进一步的 BFS 遍历
于 2013-09-13T18:07:41.933 回答