0

问题类似于“给你一组员工 id 和经理 id，经理也是一名员工。给定任何 2 个员工 id，任务是找到它们之间的关系”

我想到了创建树的方法，然后找到最低共同祖先，然后找到关系。

但是，我在创建树时遇到了问题。最初，我可以有不相关的输入，即前两个元素之间不需要有直接关系（我给出了员工 ID 和他们的经理 ID。假设前两个条目是--“emp-id-： 1 and mangr-id-2" 和 "emp-id: 3, manager id:4"，那么我会有两个根，一个有4，一个child 3，另一个root=2，和child 1，没有关系。

有了完整的数据集，就会有关系。如何解决这个问题

注意：在一个文件中，我提供了完整的数据集，如果您制作树，最终它们将连接起来。

另外，一个经理可以有两个以上的初级，所以二叉树是行不通的。

4

1 回答 1

1

您最初可以建立一个森林，当您建立连接时，加入森林中的树木。

如果雇佣关系确实是树状的，那么这样做你最终会得到一棵树 - 正如预期的那样。

关于“无二叉树” - 没问题，使用广义树。实现（使用类 java 语言）类似于：

class Node<Key> {
    Node<Key> father;
    final Key root;
    final List<Node<Key>> sons = new LinkedList<Node<Key>>();
    //constructor, methods and more fields if needed
}

还有一件事 - 我将添加一个额外的字典（基于哈希/基于树）以从员工/经理键映射到代表该员工的节点对象。
如果使用上述数据结构，地图将类似于Map<Key, Node<Key>>.

于 2013-07-20T08:51:49.590 回答