我的棘手问题是为将根据txt文件中的列表创建的通用树找到LCA。我正在寻找最有效的实现。数据的形式为：
ID，信息，ParentId
数据不会以任何方式排序。我当时正在考虑创建一棵树，但这至少需要O（nlogn）。虽然对数不是2。它取决于我假设的子级平均数。
相反，如果我将节点存储在哈希表中，那么查找LCA胜于O（nlogn）。对？对于目标节点的每个父节点，我必须检查源节点是否已访问它（假设我们从源节点开始直到根节点，并将所有父节点标记为已访问），这需要O （登录）。既然，我们只检查父母，那会比O（nlogn）好。
有更好的主意吗？
最佳答案
假设您的树以某种方式平衡了，即O（logn）高度，您的哈希表数据结构应提供O（n）算法。
从源和目标到根的第一次跟踪。您将有两条长度为O（logn）的路径。例如。 SXYZR和DWYZR。 S和D是源和目标。 R是根。这需要O（logn）时间。
然后，您可以找到最长的后缀YZR。 Y将是LCA。这需要O（logn）时间。
请记住，您需要O（n）时间来读取输入并构建哈希表。