c# - 返回层次结构中的老板-尝试应用深度优先搜索

XYZ是一家拥有CEO比尔和员工等级制度的公司员工可以有一个向他们报告的其他员工的列表，他们自己也可以有报告，等等。至少有一份报告的员工称为经理。
请执行closestcommonmanager方法，以找到距离两名员工最近的经理（即距离ceo最远的经理）。你可以假设所有员工最终都向首席执行官汇报。
样本数据：
首席执行官比尔有3名员工向他汇报工作：{Dom，Samir，Michael}
多姆有三份报告{彼得，鲍勃，波特}
萨米尔没有报告{}迈克尔没有报告{}
彼得有两份报告{米尔顿，尼娜}鲍勃没有报告{}
波特没有报告{}米尔顿没有报告{}
尼娜没有报告{}
示例调用：
closestcommonmanager（米尔顿，尼娜）=彼得
closestCommonManager（Nina，Porter）=Dom
closestcommonmanager（nina，samir）=比尔
closestcommonmanager（彼得，尼娜）=彼得
现在，为了解决这个问题，我已经这样做了——但我还没有找到解决办法。
我尝试过使用简单的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;
    }

最佳答案

这看起来像是对http://en.wikipedia.org/wiki/Lowest_common_ancestor的请求。聪明的算法通常在树上做一些预处理。一个简单的方法是标记树中每个元素与根的距离。然后要找到两个节点最接近的共同祖先，首先将指针从较低的一个向上移动，使它们都处于相同的深度，然后将两个指针一起向上移动，直到指针接触为止如果不进行预处理，可以同时从两个节点向上移动，将看到的所有节点添加到集合，并检查何时将节点添加到已存在的节点集合。在这两种情况下，第一次遇到两边的节点时，该节点是最低的公共祖先。

关于c# - 返回层次结构中的老板-尝试应用深度优先搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25072591/