1

私は、この質問が何度も聞かれたことを知っています。バイナリ ツリー (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の仕組みですか?

4

1 に答える 1