algorithm - 给定节点对的最低公共(public)祖先

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很好地解释了事情。如果您有任何问题，请回帖。