algorithm - 我的最低共同祖先算法给出了与在线找到的其他算法不同但逻辑上正确的答案

Question

我正在编写一个程序来查找二叉搜索树中一对节点的最低公共(public)祖先(假定元素存在于树中)。我的逻辑是:

1. 从根开始。
2. 如果两个元素都大于当前元素，则返回根(这是不同之处)。
3. 否则如果都小于根，则在左子树上递归。
4. 否则返回根(一个较小，另一个较大)。

然而，Algos 在线发现(http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html)改变了第 2 步，在这种情况下，它们在右子树上递归，因此对于以下树:

  2
 / \
1   4
   / \
  3   5

然后输入3和5，我的算法给出 2，而其他算法给出 4 作为输出。

那么，是我理解 LCA 的定义错误(因为 2 小于 4 并且是共同祖先)还是我的 Algo 正确。

Answer 1

T 中 v 和 w 的 LCA 是距离根最远的 v 和 w 的共享祖先。因此，在线版本是正确的，与您的理解不同。

看看这个 LCA definition

如果你愿意，你也可以避免递归。只需从您的候选者追踪路由回到根节点。第一个公共(public)节点是LCA