二叉树的 LCA - 需要一些建议

Question

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

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

(3,11) 的代码 returns 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 是如何工作的？

Answer 1

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

我认为您可能忽略了 the definition of LCA 中的一点，其中元素被视为其自身的后代：

...the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

（强调我的）

由于 3 是 11 的子代，因此 LCA 是 11。

二叉树的 LCA - 需要一些建议

LCA of Binary Tree - Need some Advice

java

binary-tree

lowest-common-ancestor