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

Question

XYZ 是一家拥有 CEO Bill 和员工等级制度的公司。员工可以有一份向他们报告的其他员工的列表，这些员工自己也可以有报告，等等。至少拥有一份报告的员工称为经理。请实现 closestCommonManager 方法以找到距离两名员工最近的经理(即离 CEO 最远的经理)。您可能会假设所有员工最终都会向 CEO 汇报。

示例数据:首席执行官比尔有 3 名员工向他汇报:{Dom、Samir、Michael}

Dom 有三个报告 { Peter, Bob, Porter}

Samir 没有报告 {}Michael 没有报告{}

Peter 有 2 个报告{Milton, Nina} Bob 没有报告{}

Porter 没有报告 {} Milton 没有报告{}

Nina 没有报告{}

调用示例:closestCommonManager(Milton, Nina) = 彼得

closestCommonManager(Nina, Porter) = Dom

closestCommonManager(Nina, Samir) = 比尔

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;
    }

Answer 1

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