algorithm - 有效地找到二叉搜索树中两个节点的最低公共(public)祖先

Question

只是想知道以下算法在二叉搜索树中查找两个节点的最低公共(public)祖先的效率如何。

Node getLowestCommonAncestor (Node root, Node a, Node b) {

   Find the in-order traversal of Node root.
   Find temp1 = the in-order successor of Node a.
   Find temp2 = the in-order successor of Node b.

   return min (temp1, temp2);
}

Answer 1

在二叉搜索树中搜索最低公共(public)祖先比这更简单:观察 LCA 是对项目 A 和项目 B 的搜索第一次发生分歧的节点。

从根开始，同时查找A和B。只要两次搜索都将您带向同一方向，就继续搜索。一旦您到达节点，搜索 A 和 B 会将您带到不同的子树，您就知道当前节点是 LCA。