给定节点对的最低公共祖先

Question

我被这个问题偶然发现。以下是我的做法：

Lets say the two nodes are node1 and node2 
For any node (lets say node1), find the path from Root to 
     node1 and store it in an HashMap 
For the other node node2, find the path from root to node2, and while traversing back, 
     check if any of the nodes are present in the hashmap or not 
Return the first found node 

时间复杂度为O（n）和空间复杂度也是O（h）时，其中n是树的高度

我只是想知道有多好，这种方法。或者是否存在其他更好的解决方案。

编辑：给定的树是二叉树，而不是BST。因此，查找节点所花的时间与节点的大小是线性的。

Answer 1

如果你只需要这样做一次（或几次），那么这是一个好方法（如果可能的话，你可以通过从节点到根的方式进行优化）。如果你需要为不同的节点对做很多次这样的事情，那么花费更多的时间对某些事情进行预计算是值得的，这将加快查询速度。

我认为this article解释得很好。如果您有任何问题，请发回。

Answer 2

树如何表示？特别是，是否有对任何树节点的父节点的引用？它是一棵有序的树吗？

计算从节点到根的路径并不比较简单，然后比较从根节点到节点的路径？两条路径上的最后一个节点是共同的祖先。

我想找到从根到节点的路径（如你的做法有它）是O（n），其中n是树的大小，除非树是有序的...

所以你的方法作品，但如果我问你的问题，我本来希望你问一些关于树的布局的额外问题，以确定正确的答案...

Answer 3

这里是解决最低公共祖先问题的指令。

[范围最小查询和最近公共祖先] [1]

[1]：http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest共同祖先（LCA）