返回层次结构中的Boss --尝试应用深度优先搜索
XYZ是一家拥有首席执行官比尔和员工等级制度的公司。员工可以拥有向他们报告的其他员工的列表，这些员工自己也可以有报告，依此类推。至少有一个报告的员工称为经理。请实现closestCommonManager方法来查找离两个员工最近的经理(即离首席执行官最远)。你可以假设所有员工最终都会向首席执行官汇报工作。
示例数据: CEO Bill有3名员工向他汇报工作：{Dom，Samir，Michael}
Dom有三个报告{ Peter，Bob，Porter}
Samir没有报告{} Michael没有报告{}
Peter有2个报告{Milton，Nina} Bob没有报告{}
波特没有报告{}弥尔顿没有报告{}
Nina没有报告{}
示例调用: closestCommonManager(Milton，Nina) = Peter
closestCommonManager(妮娜，波特)= Dom
closestCommonManager(妮娜，萨米尔)=比尔
closestCommonManager( Peter，Nina) =Peter
现在，为了解决这个问题，我采用了这样的方法--但我还没有得到解决方案。我曾尝试使用简单的DFS算法，但无法完成解决方案。
public static Employee closestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee)
{
var visited = new HashSet<Employee>();
bool firstFound = false, secondFound = false;
Stack<Employee> stack = new Stack<Employee>(); // DFS
stack.Push(ceo);
while (stack.Count != 0)
{
Employee current = stack.Pop();
IList<Employee> employeeList = current.getReports();
if (firstEmployee.getId() == current.getId())
{
firstFound = true;
}
else if (secondEmployee.getId() == current.getId())
{
secondFound = true;
}
if (firstFound && secondFound)
return current;
// Should i return previous one? how do i keep track of the
// node which i found first in hierarchy ???
Console.WriteLine(current.getName());
foreach (var employee in employeeList)
{
if (visited.Add(employee))
{
stack.Push(employee);
}
}
}
return null;
}回答 6
Stack Overflow用户
发布于 2014-08-01 12:58:31
这看起来像是对http://en.wikipedia.org/wiki/Lowest_common_ancestor的请求。为此，聪明的算法通常会对树进行一些预处理。一种简单的方法是标记树中的每个元素与根的距离。然后，为了找到两个节点最接近的共同祖先，首先将指针从下一个节点向上移动，使它们都在相同的深度，然后一起向上移动两个指针，直到指针接触。如果您没有进行预处理，您可以同时从两个节点向上移动，将您看到的所有节点添加到一个集合中，并检查何时将节点添加到遇到的已有节点集中。在任何一种情况下，当您第一次遇到来自两端的节点时，该节点都是最低的公共祖先。
Stack Overflow用户
发布于 2014-08-01 13:07:29
使用DFS的简单解决方案
单独的任务。
创建DFS函数以查找从root到worker的路径。(列表或堆栈)
为两个worker调用它，然后比较从root到worker的路径。
最后一场比赛是你的目标
Stack Overflow用户
发布于 2014-08-01 12:58:15
在这个解决方案中，我向Employee添加了两个字段
//all managers of this Employee
public List<Employee> Bosses = new List<Employee>();
//how many managers between employee and Ceo
public int DistanceFromCeo = 0;此代码查找第一个和第二个员工的所有老板，并将它们存储在其Bosses字段中
var stack = new Stack<Employee>(); // DFS
stack.Push(ceo);
while (stack.Count != 0)
{
var current = stack.Pop();
IList<Employee> employeeList = current.getReports();
foreach (var employee in employeeList)
{
employee.Bosses.AddRange(current.Bosses);
employee.Bosses.Add(current);
employee.DistanceFromCeo = current.DistanceFromCeo + 1;
if (firstEmployee.getId() == employee.getId())
{
firstEmployee.Bosses.AddRange(employee.Bosses);
}
if (secondEmployee.getId() == employee.getId())
{
secondEmployee.Bosses.AddRange(employee.Bosses);
}
stack.Push(employee);
}
}现在很容易得到答案-加入老板并找到最远的：
var commonBosses = (from f in firstEmployee.Bosses
join s in firstEmployee.Bosses on f.getId() equals s.getId()
select f).ToList();
var maxLenght = commonBosses.Max(b => b.DistanceFromCeo);
return commonBosses.FirstOrDefault(b => b.DistanceFromCeo == maxLenght);只有当层次结构中没有循环时，它才会起作用。但我猜，如果有循环，那么就不清楚谁是最远的，如果你运行整个循环，dinstance将无限增长。
https://stackoverflow.com/questions/25072591
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号