私は、この質問が何度も聞かれたことを知っています。バイナリ ツリー (BST ではない) の LCA について明確にする必要があります。指定されたツリーから 2 つのノード (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;
}
}
}
ここで私は混乱しています。それは正しいはずです。間違っている場合は修正してください。ここで混乱していますか?またはそれはLCAの仕組みですか?