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

我被这个问题绊倒了。以下是我的方法:

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。因此,查找节点所用的时间与节点的大小是线性的。