algorithm - My Lowest Common Ancestor Algo 给出的答案与网上找到的其他算法不同，但在逻辑上是正确的

Question

我正在编写一个程序，用于在二叉搜索树中查找一对节点的最低共同祖先（假设树中存在元素）。我的逻辑是：

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 并且是共同祖先）还是我的算法正确。

Answer 1

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

查看此LCA 定义

如果你愿意，你也可以避免递归。只需将路线从您的候选人追溯到根节点。第一个公共节点是 LCA