我知道这个问题已经被问过很多次了。我需要对二叉树（不是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是如何工作的？
最佳答案
在显示的树中，11是(3, 11)的正确LCA。
我认为您可能忽略了the definition of LCA中的元素，在这些元素中元素被视为自身的后代：
...树或有向无环图（DAG）中两个节点v和w的最低公共祖先（LCA）是同时具有v和w作为后代的最低（即最深）节点，我们将每个节点定义为自身的后代（因此，如果v与w有直接联系，则w是最低的共同祖先）。
（强调我的）
由于3是11的子级，因此LCA是11。