1

我知道这个问题已经被问过很多次了。我需要对二叉树（不是 BST）的 LCA 进行一些澄清。如果我试图从给定的树中找到两个节点（3,11）的 LCA：

    _______1______
   /              \
 ___2__          ___4__
/      \        /      \
6       5       9       11
                       /  \
                       7   3

代码为 (3,11) 返回 11。

 // Binary Tree LCA not BST
 private Node findLowestCommonAncestor(Node root, int value1, int value2) {

Node leftLCA = null;
Node rightLCA = null;

if (root == null) {
  return null;
}

else {
  int value = root.item;

  if (value == value1 || value == value2) {
    return root;

  }

  else {

    leftLCA = findLowestCommonAncestor(root.left, value1, value2);
    rightLCA = findLowestCommonAncestor(root.right, value1, value2);

    if (leftLCA != null && rightLCA != null) {
      return root;
    }

    return (leftLCA != null) ? leftLCA : rightLCA;
  }
}

}

在这里我很困惑，应该是4对。如果我错了，请纠正我。我在这里感到困惑吗？还是 LCA 是如何工作的？

4

1 回答 1

0

11(3, 11)是您显示的树中的正确 LCA 。

我想你可能忽略了LCA 定义中元素被认为是它们自己的后代的一点：

...树或有向无环图 (DAG) 中两个节点 v 和 w 的最低共同祖先 (LCA) 是具有 v 和 w 作为后代的最低（即最深）节点，我们将每个节点定义为自身的后代（因此，如果 v 与 w 有直接联系，则 w 是最低的共同祖先）。

（强调我的）

既然3是孩子11，LCA就是11。

于 2015-10-12T21:03:27.993 回答