algorithm - lca - ¿Cómo encontrar el ancestro común más bajo de dos nodos en cualquier árbol binario?

lca geeksforgeeks

Question

El árbol binario aquí no necesariamente es un árbol de búsqueda binario.
La estructura podría tomarse como:

struct node {
    int data;
    struct node *left;
    struct node *right;
};

La solución máxima que pude resolver con un amigo fue algo así:
Considera este árbol binario :

Binary Tree http://lcm.csa.iisc.ernet.in/dsa/img151.gif

Los rendimientos del recorrido inorden - 8, 4, 9, 2, 5, 1, 6, 3, 7

Y los rendimientos del recorrido del postorder: 8, 9, 4, 5, 2, 6, 7, 3, 1

Entonces, por ejemplo, si queremos encontrar el ancestro común de los nodos 8 y 5, hacemos una lista de todos los nodos que están entre 8 y 5 en el recorrido del árbol inorden, que en este caso es [4, 9 , 2]. Luego, verificamos qué nodo en esta lista aparece último en el recorrido del postorder, que es 2. De ahí que el ancestro común para 8 y 5 sea 2.

La complejidad de este algoritmo, creo que es O (n) (O (n) para atravesar inorder / postorder, el resto de los pasos son O (n) dado que no son más que simples iteraciones en matrices. Pero hay una gran posibilidad de que esto esté mal. :-)

Pero este es un enfoque muy crudo, y no estoy seguro de si se rompe en algún caso. ¿Hay alguna otra solución (posiblemente más óptima) para este problema?

Answer 1

Aquí está el código de trabajo en JAVA

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

Answer 2

Aquí está la forma C ++ de hacerlo. He tratado de mantener el algoritmo lo más fácil posible para comprender:

// Assuming that `BinaryNode_t` has `getData()`, `getLeft()` and `getRight()`
class LowestCommonAncestor
{
  typedef char type;    
  // Data members which would behave as place holders
  const BinaryNode_t* m_pLCA;
  type m_Node1, m_Node2;

  static const unsigned int TOTAL_NODES = 2;

  // The core function which actually finds the LCA; It returns the number of nodes found
  // At any point of time if the number of nodes found are 2, then it updates the `m_pLCA` and once updated, we have found it!
  unsigned int Search (const BinaryNode_t* const pNode)
  {
    if(pNode == 0)
      return 0;

    unsigned int found = 0;

    found += (pNode->getData() == m_Node1);
    found += (pNode->getData() == m_Node2);

    found += Search(pNode->getLeft()); // below condition can be after this as well
    found += Search(pNode->getRight());

    if(found == TOTAL_NODES && m_pLCA == 0)
      m_pLCA = pNode;  // found !

    return found;
  }

public:
  // Interface method which will be called externally by the client
  const BinaryNode_t* Search (const BinaryNode_t* const pHead,
                              const type node1,
                              const type node2)
  {
    // Initialize the data members of the class
    m_Node1 = node1;
    m_Node2 = node2;
    m_pLCA = 0;

    // Find the LCA, populate to `m_pLCANode` and return
    (void) Search(pHead);
    return m_pLCA;
  }
};

Cómo usarlo:

LowestCommonAncestor lca;
BinaryNode_t* pNode = lca.Search(pWhateverBinaryTreeNodeToBeginWith);
if(pNode != 0)
  ...

Answer 3

Aquí hay dos enfoques en c # (.net) (ambos discutidos arriba) para referencia:

1. Versión recursiva de encontrar LCA en árbol binario (O (N) - como máximo se visita cada nodo) (los puntos principales de la solución es LCA es (a) único nodo en árbol binario donde ambos elementos residen a ambos lados de los subárboles (izquierda y a la derecha) es LCA. (b) Y tampoco importa qué nodo esté presente en cada lado, inicialmente traté de mantener esa información, y obviamente la función recursiva se volvió tan confusa. Una vez que me di cuenta, se volvió muy elegante.

2. Buscando ambos nodos (O (N)) y haciendo un seguimiento de los caminos (usa espacio extra, entonces, el # 1 es probablemente superior incluso si el espacio es probablemente insignificante si el árbol binario está bien equilibrado ya que el consumo de memoria adicional será justo O (log (N)).

   para que las rutas sean comparadas (similarmente similar a la respuesta aceptada, pero las rutas se calculan suponiendo que el nodo del puntero no está presente en el nodo del árbol binario)

3. Solo para completar ( no relacionado con la pregunta ), LCA en BST (O (log (N))

4. Pruebas

Recursivo:

private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode, 
            int e1, int e2)
        {
            Debug.Assert(e1 != e2);

            if(treeNode == null)
            {
                return null;
            }
            if((treeNode.Element == e1)
                || (treeNode.Element == e2))
            {
                //we don''t care which element is present (e1 or e2), we just need to check 
                //if one of them is there
                return treeNode;
            }
            var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2);
            var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2);
            if(nLeft != null && nRight != null)
            {
                //note that this condition will be true only at least common ancestor
                return treeNode;
            }
            else if(nLeft != null)
            {
                return nLeft;
            }
            else if(nRight != null)
            {
                return nRight;
            }
            return null;
        }

donde se invoca la versión recursiva privada anterior mediante el siguiente método público:

public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2)
        {
            var n = this.FindNode(this._root, e1);
            if(null == n)
            {
                throw new Exception("Element not found: " + e1);
            }
            if (e1 == e2)
            {   
                return n;
            }
            n = this.FindNode(this._root, e2);
            if (null == n)
            {
                throw new Exception("Element not found: " + e2);
            }
            var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2);
            if (null == node)
            {
                throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2));
            }
            return node;
        }

Solución al realizar un seguimiento de las rutas de ambos nodos:

public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2)
        {
            var path1 = new List<BinaryTreeNode>();
            var node1 = this.FindNodeAndPath(this._root, e1, path1);
            if(node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e1));
            }
            if(e1 == e2)
            {
                return node1;
            }
            List<BinaryTreeNode> path2 = new List<BinaryTreeNode>();
            var node2 = this.FindNodeAndPath(this._root, e2, path2);
            if (node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e2));
            }
            BinaryTreeNode lca = null;
            Debug.Assert(path1[0] == this._root);
            Debug.Assert(path2[0] == this._root);
            int i = 0;
            while((i < path1.Count)
                && (i < path2.Count)
                && (path2[i] == path1[i]))
            {
                lca = path1[i];
                i++;
            }
            Debug.Assert(null != lca);
            return lca;
        }

donde FindNodeAndPath se define como

private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path)
        {
            if(node == null)
            {
                return null;
            }
            if(node.Element == e)
            {
                path.Add(node);
                return node;
            }
            var n = this.FindNodeAndPath(node.Left, e, path);
            if(n == null)
            {
                n = this.FindNodeAndPath(node.Right, e, path);
            }
            if(n != null)
            {
                path.Insert(0, node);
                return n;
            }
            return null;
        }

BST (LCA) - no relacionado (solo para completarlo como referencia)

public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
        {
            //ensure both elements are there in the bst
            var n1 = this.BstFind(e1, throwIfNotFound: true);
            if(e1 == e2)
            {
                return n1;
            }
            this.BstFind(e2, throwIfNotFound: true);
            BinaryTreeNode leastCommonAcncestor = this._root;
            var iterativeNode = this._root;
            while(iterativeNode != null)
            {
                if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
                {
                    iterativeNode = iterativeNode.Left;
                }
                else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
                {
                    iterativeNode = iterativeNode.Right;
                }
                else
                {
                    //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                    return iterativeNode;
                }
            }
            //control will never come here
            return leastCommonAcncestor;
        }

Pruebas unitarias

[TestMethod]
        public void LeastCommonAncestorTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
            }
            for(int i = 0; i < b.Length; i++)
            {
                var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
                Assert.IsTrue(n.Element == b[i]);
                var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]);
                Assert.IsTrue(n1.Element == b[i]);
                Assert.IsTrue(n == n1);
                var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]);
                Assert.IsTrue(n2.Element == b[i]);
                Assert.IsTrue(n2 == n1);
                Assert.IsTrue(n2 == n);
            }
        }

Answer 4

Aunque esto ya se ha respondido, este es mi enfoque para este problema utilizando el lenguaje de programación C. Aunque el código muestra un árbol de búsqueda binario (en lo que respecta a insert ()), pero el algoritmo también funciona para un árbol binario. La idea es recorrer todos los nodos que se encuentran del nodo A al nodo B en el cruce interno, buscar los índices para estos en el recorrido del pedido posterior. El nodo con índice máximo en el recorrido posterior de la orden es el ancestro común más bajo.

Este es un código C que funciona para implementar una función para encontrar el ancestro común más bajo en un árbol binario. También proporciono todas las funciones de utilidad, etc., pero salte a CommonAncestor () para una comprensión más rápida.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

static inline int min (int a, int b)
{
    return ((a < b) ? a : b);
}
static inline int max (int a, int b)
{
    return ((a > b) ? a : b);
}

typedef struct node_ {
    int value;
    struct node_ * left;
    struct node_ * right;
} node;

#define MAX 12

int IN_ORDER[MAX] = {0};
int POST_ORDER[MAX] = {0};

createNode(int value) 
{
    node * temp_node = (node *)malloc(sizeof(node));
    temp_node->left = temp_node->right = NULL;
    temp_node->value = value;
    return temp_node;
}

node *
insert(node * root, int value)
{
    if (!root) {
        return createNode(value);
    }

    if (root->value > value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }

    return root;
}


/* Builds inorder traversal path in the IN array */
void
inorder(node * root, int * IN)
{
    static int i = 0;

    if (!root) return;

    inorder(root->left, IN);
    IN[i] = root->value;
    i++;
    inorder(root->right, IN);
}

/* Builds post traversal path in the POST array */

void
postorder (node * root, int * POST)
{
    static int i = 0;

    if (!root) return;

    postorder(root->left, POST);
    postorder(root->right, POST);
    POST[i] = root->value;
    i++;
}


int
findIndex(int * A, int value)
{
    int i = 0;
    for(i = 0; i< MAX; i++) {
        if(A[i] == value) return i;
    }
}
int
CommonAncestor(int val1, int val2)
{
    int in_val1, in_val2;
    int post_val1, post_val2;
    int j=0, i = 0; int max_index = -1;

    in_val1 = findIndex(IN_ORDER, val1);
    in_val2 = findIndex(IN_ORDER, val2);
    post_val1 = findIndex(POST_ORDER, val1);
    post_val2 = findIndex(POST_ORDER, val2);

    for (i = min(in_val1, in_val2); i<= max(in_val1, in_val2); i++) {
        for(j = 0; j < MAX; j++) {
            if (IN_ORDER[i] == POST_ORDER[j]) {
                if (j > max_index) {
                    max_index = j;
                }
            }
        }
    }
    printf("/ncommon ancestor of %d and %d is %d/n", val1, val2, POST_ORDER[max_index]);
    return max_index;
}
int main()
{
    node * root = NULL; 

    /* Build a tree with following values */
    //40, 20, 10, 30, 5, 15, 25, 35, 1, 80, 60, 100
    root = insert(root, 40);
    insert(root, 20);
    insert(root, 10);
    insert(root, 30);
    insert(root, 5);
    insert(root, 15);
    insert(root, 25);
    insert(root, 35);
    insert(root, 1);
    insert(root, 80);
    insert(root, 60);
    insert(root, 100);

    /* Get IN_ORDER traversal in the array */
    inorder(root, IN_ORDER);

    /* Get post order traversal in the array */
    postorder(root, POST_ORDER);

    CommonAncestor(1, 100);


}

Answer 5

Bueno, este tipo de depende de cómo está estructurado tu árbol binario. Presumiblemente, tiene alguna forma de encontrar el nodo de hoja deseado dada la raíz del árbol; simplemente, aplique eso a ambos valores hasta que las ramas que elija diverjan.

Si no tiene forma de encontrar la hoja deseada con la raíz, entonces su única solución, tanto en operación normal como para encontrar el último nodo común, es una búsqueda de fuerza bruta en el árbol.

Answer 6

Comenzando desde el nodo root y moviéndose hacia abajo si encuentra cualquier nodo que tenga q como su hijo directo, entonces es el LCA. (editar - esto debería ser si p o q es el valor del nodo, devuélvalo. De lo contrario, fallará cuando uno de p o q sea ​​un hijo directo del otro).

De lo contrario, si encuentra un nodo con p en su subárbol derecho (o izquierdo) q en su subárbol izquierdo (o derecho), entonces es el LCA.

El código fijo se ve así:

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

El código siguiente falla cuando cualquiera es hijo directo de otro.

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is direct child of root then root is LCA.
        if(root->left==p || root->left==q || 
           root->right ==p || root->right ==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Código en acción

Answer 7

Considera este árbol

Si hacemos postorder y preorden transversal y encontramos el primer predecesor común y sucesor, obtenemos el ancestro común.

postorder => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 preorder => 7,3,1,0,2,6,4 , 5,12,9,8,11,10,13,15,14

• Ej .: 1

Antepasado común mínimo de 8,11

en postorder tenemos => 9,14,15,13,12,7 después de 8 y 11 en preorder tenemos => 7,3,1,0,2,6,4,5,12,9 antes de 8 y 11

9 es el primer número común que ocurre después de 8 y 11 en postorder y antes de 8 y 11 en preorden, por lo tanto, 9 es la respuesta

• Ej .: 2

Ancestro común menos de 5,10

11,9,14,15,13,12,7 en postorder 7,3,1,0,2,6,4 en preorden

7 es el primer número que ocurre después de 5,10 en postorder y antes de 5,10 en preorden, por lo tanto, 7 es la respuesta

Answer 8

El algoritmo recursivo siguiente se ejecutará en O (log N) para un árbol binario equilibrado. Si cualquiera de los nodos pasados ​​a la función getLCA () es el mismo que el raíz, entonces la raíz será el LCA y no habrá necesidad de realizar ningún recursión.

Casos de prueba. [1] Ambos nodos n1 y n2 están en el árbol y residen en cualquier lado de su nodo padre. [2] O bien el nodo n1 o n2 es la raíz, el LCA es la raíz. [3] Solo n1 o n2 están en el árbol, LCA será el nodo raíz del subárbol izquierdo de la raíz del árbol, o el LCA será el nodo raíz del subárbol derecho de la raíz del árbol.

[4] Ni n1 ni n2 están en el árbol, no hay LCA. [5] Tanto n1 como n2 están en línea recta uno al lado del otro, LCA será cualquiera de n1 o n2 que esté siempre cerca de la raíz del árbol.

//find the search node below root
bool findNode(node* root, node* search)
{
    //base case
    if(root == NULL)
        return false;

    if(root->val == search->val)
        return true;

    //search for the node in the left and right subtrees, if found in either return true
    return (findNode(root->left, search) || findNode(root->right, search));
}

//returns the LCA, n1 & n2 are the 2 nodes for which we are
//establishing the LCA for
node* getLCA(node* root, node* n1, node* n2)
{
    //base case
    if(root == NULL)
        return NULL;

    //If 1 of the nodes is the root then the root is the LCA
    //no need to recurse.
    if(n1 == root || n2 == root)
        return root;

    //check on which side of the root n1 and n2 reside
    bool n1OnLeft = findNode(root->left, n1);
    bool n2OnLeft = findNode(root->left, n2);

    //n1 & n2 are on different sides of the root, so root is the LCA
    if(n1OnLeft != n2OnLeft)
        return root;

    //if both n1 & n2 are on the left of the root traverse left sub tree only
    //to find the node where n1 & n2 diverge otherwise traverse right subtree
    if(n1OnLeft)
        return getLCA(root->left, n1, n2);
    else
        return getLCA(root->right, n1, n2);
}

Answer 9

En Scala, el código es:

abstract class Tree
case class Node(a:Int, left:Tree, right:Tree) extends Tree
case class Leaf(a:Int) extends Tree

def lca(tree:Tree, a:Int, b:Int):Tree = {
tree match {
case Node(ab,l,r) => {
if(ab==a || ab ==b) tree else {
    val temp = lca(l,a,b);
    val temp2 = lca(r,a,b);
    if(temp!=null && temp2 !=null)
        tree
    else if (temp==null && temp2==null) 
        null
    else if (temp==null) r else l
}

}
case Leaf(ab) => if(ab==a || ab ==b) tree else null
}
}

Answer 10

Encontré una solución

1. Tomar en orden
2. Tomar preorden
3. Tomar postorder

Dependiendo de 3 travesías, puede decidir quién es el LCA. De LCA, encuentre la distancia de ambos nodos. Agregue estas dos distancias, que es la respuesta.

Answer 11

Esto es lo que pienso,

1. Encuentre la ruta para el primer nodo, guárdelo en arr1.
2. Comience a encontrar la ruta para el nodo 2, mientras lo hace, compruebe cada valor desde la raíz hasta arr1.
3. tiempo cuando el valor es diferente, salga. El antiguo valor coincidente es el LCA.

Complejidad: paso 1: O (n), paso 2 = ~ O (n), total = ~ O (n).

Answer 12

Esto se puede encontrar en: http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

 tree_node_type *LowestCommonAncestor(
 tree_node_type *root , tree_node_type *p , tree_node_type *q)
 {
     tree_node_type *l , *r , *temp;
     if(root==NULL)
     {
        return NULL;
     }

    if(root->left==p || root->left==q || root->right ==p || root->right ==q)
    {
        return root;
    }
    else
    {
        l=LowestCommonAncestor(root->left , p , q);
        r=LowestCommonAncestor(root->right , p, q);

        if(l!=NULL && r!=NULL)
        {
            return root;
        }
        else
        {
        temp = (l!=NULL)?l:r;
        return temp;
        }
    }
}

Answer 13

He intentado con imágenes ilustrativas y código de trabajo en Java,

http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html

Answer 14

Intenta así

node * lca(node * root, int v1,int v2)
{

if(!root) {
            return NULL;
    }
    if(root->data == v1 || root->data == v2) {
        return root;}
    else
    {
        if((v1 > root->data && v2 < root->data) || (v1 < root->data && v2 > root->data))
        {
            return root;
        }

        if(v1 < root->data && v2 < root->data)
        {
            root = lca(root->left, v1, v2);
        }

        if(v1 > root->data && v2 > root->data)
        {
            root = lca(root->right, v1, v2);
        }
    }
return root;
}

Answer 15

La forma más fácil de encontrar al Ancestro común más bajo es utilizando el siguiente algoritmo:

Examine root node if value1 and value2 are strictly less that the value at the root node Examine left subtree else if value1 and value2 are strictly greater that the value at the root node Examine right subtree else return root

public int LCA(TreeNode root, int value 1, int value 2) {
    while (root != null) {
       if (value1 < root.data && value2 < root.data)
           return LCA(root.left, value1, value2);
       else if (value2 > root.data && value2 2 root.data)
           return LCA(root.right, value1, value2);
       else
           return root
    }

    return null;
} 

Answer 16

Las respuestas dadas hasta ahora usan recursiones o tiendas, por ejemplo, un camino en la memoria.

Ambos enfoques pueden fallar si tienes un árbol muy profundo.

Aquí está mi opinión sobre esta pregunta. Cuando verificamos la profundidad (distancia desde la raíz) de ambos nodos, si son iguales, podemos movernos hacia arriba desde ambos nodos hacia el ancestro común. Si una de las profundidades es más grande, debemos movernos hacia arriba desde el nodo más profundo mientras permanecemos en la otra.

Aquí está el código:

findLowestCommonAncestor(v,w):
  depth_vv = depth(v);
  depth_ww = depth(w);

  vv = v; 
  ww = w;

  while( depth_vv != depth_ww ) {
    if ( depth_vv > depth_ww ) {
      vv = parent(vv);
      depth_vv--;
    else {
      ww = parent(ww);
      depth_ww--;
    }
  }

  while( vv != ww ) {
    vv = parent(vv);
    ww = parent(ww);
  }

  return vv;    

La complejidad de tiempo de este algoritmo es: O (n). La complejidad del espacio de este algoritmo es: O (1).

Con respecto al cálculo de la profundidad, primero podemos recordar la definición: si v es raíz, profundidad (v) = 0; De lo contrario, depth (v) = depth (parent (v)) + 1. Podemos calcular la profundidad de la siguiente manera:

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;

Answer 17

Nick Johnson tiene razón en que un algoritmo de complejidad de tiempo O (n) es lo mejor que puede hacer si no tiene punteros padres. Para una versión recursiva simple de ese algoritmo, vea el código en la publicación de Kinding que se ejecuta en O (n) tiempo .

Pero tenga en cuenta que si sus nodos tienen punteros de los padres, es posible un algoritmo mejorado. Para ambos nodos en cuestión, construya una lista que contenga la ruta de la raíz al nodo comenzando en el nodo, y el frente insertando el padre.

Entonces para 8 en tu ejemplo, obtienes (mostrando los pasos): {4}, {2, 4}, {1, 2, 4}

Haz lo mismo para tu otro nodo en cuestión, lo que resulta en (pasos no mostrados): {1, 2}

Ahora compare las dos listas que hizo buscando el primer elemento donde difiere la lista, o el último elemento de una de las listas, lo que ocurra primero.

Este algoritmo requiere O (h) tiempo donde h es la altura del árbol. En el peor de los casos, O (h) es equivalente a O (n), pero si el árbol está equilibrado, eso es solo O (log (n)). También requiere O (h) espacio. Es posible una versión mejorada que usa solo espacio constante, con código que se muestra en la publicación de CEGRD

Independientemente de cómo se construya el árbol, si esta será una operación que realiza muchas veces en el árbol sin cambiarla en el medio, hay otros algoritmos que puede usar que requieren la preparación de tiempo O (n) [lineal], pero luego encontrar cualquier el par toma solo O (1) [constante] el tiempo. Para referencias a estos algoritmos, vea la página del problema ancestro común más baja en Wikipedia . (Crédito a Jason por publicar originalmente este enlace)

Answer 18

Para averiguar el ancestro común de dos nodos: -

• Encuentre el nodo Node1 dado en el árbol utilizando la búsqueda binaria y guarde todos los nodos visitados en este proceso en una matriz, digamos A1. Tiempo - O (logn), Espacio - O (logn)
• Encuentre el Nodo2 dado en el árbol usando la búsqueda binaria y guarde todos los nodos visitados en este proceso en una matriz, digamos A2. Tiempo - O (logn), Espacio - O (logn)
• Si la lista A1 o la lista A2 están vacías, entonces uno de los nodos no existe, por lo que no existe un antecesor común.
• Si la lista A1 y la lista A2 no están vacías, busque en la lista hasta encontrar un nodo que no coincida. Tan pronto como encuentre un nodo así, entonces el nodo anterior a eso es antepasado común.

Esto funcionaría para el árbol de búsqueda binario.

Answer 19

Si alguien está interesado en el pseudo código (para el hogar universitario funciona) aquí hay uno.

GETLCA(BINARYTREE BT, NODE A, NODE  B)
IF Root==NIL
    return NIL
ENDIF

IF Root==A OR root==B
    return Root
ENDIF

Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)

IF Left! = NIL AND Right! = NIL
    return root
ELSEIF Left! = NIL
    Return Left
ELSE
    Return Right
ENDIF

Answer 20

Si es un árbol binario completo con hijos del nodo x como 2 * x y 2 * x + 1, hay una forma más rápida de hacerlo

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;  
}

Como funciona

1. Obtiene los bits necesarios para representar xey, que usando la búsqueda binaria es O (log (32))
2. el prefijo común de la notación binaria de x y y es el ancestro común
3. lo que esté representado por un mayor número de bits se lleva al mismo bit por k >> diff
4. k = x ^ y borra el prefijo común de x & y
5. encontrar bits que representan el sufijo restante
6. desplaza x o y por los bits de sufijo para obtener el prefijo común que es el ancestro común.

Esto funciona porque básicamente divide el número más grande por dos recursivamente hasta que ambos números sean iguales. Ese número es el ancestro común. La división es efectivamente la operación correcta del cambio. Entonces, necesitamos encontrar el prefijo común de dos números para encontrar el ancestro más cercano

Answer 21

Simplemente camine hacia abajo desde la root todo el árbol, siempre y cuando ambos nodos dados, digamos q , para los cuales se debe encontrar el Ancestro, estén en el mismo subárbol (lo que significa que sus valores son más pequeños o mayores que los del raíz).

Esto camina directamente desde la raíz hasta el antecesor común mínimo, sin mirar el resto del árbol, por lo que es más o menos lo más rápido posible. Algunas formas de hacerlo.

Iterativo, O (1) espacio

Pitón

def lowestCommonAncestor(self, root, p, q):
    while (root.val - p.val) * (root.val - q.val) > 0:
        root = (root.left, root.right)[p.val > root.val]
    return root

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    return root;
}

en caso de desbordamiento, lo haría (root.val - (long) p.val) * (root.val - (long) q.val)

Recursivo

Pitón

def lowestCommonAncestor(self, root, p, q):
    next = p.val < root.val > q.val and root.left or /
           p.val > root.val < q.val and root.right
    return self.lowestCommonAncestor(next, p, q) if next else root

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return (root.val - p.val) * (root.val - q.val) < 1 ? root :
           lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

Answer 22

El algoritmo de antepasados ​​menos común fuera de línea de Tarjan es suficientemente bueno (véase también Wikipedia ). Hay más sobre el problema (el menor problema ancestro común) en Wikipedia .

Answer 23

Code for A Breadth First Search to make sure both nodes are in the tree. Only then move forward with the LCA search. Please comment if you have any suggestions to improve. I think we can probably mark them visited and restart the search at a certain point where we left off to improve for the second node (if it isn''t found VISITED)

public class searchTree {
    static boolean v1=false,v2=false;
    public static boolean bfs(Treenode root, int value){
         if(root==null){
           return false;
     }
    Queue<Treenode> q1 = new LinkedList<Treenode>();

    q1.add(root);
    while(!q1.isEmpty())
    {
        Treenode temp = q1.peek();

        if(temp!=null) {
            q1.remove();
            if (temp.value == value) return true;
            if (temp.left != null) q1.add(temp.left);
            if (temp.right != null) q1.add(temp.right);
        }
    }
    return false;

}
public static Treenode lcaHelper(Treenode head, int x,int y){

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

    if(head.value == x || head.value ==y){
        if (head.value == y){
            v2 = true;
            return head;
        }
        else {
            v1 = true;
            return head;
        }
    }

    Treenode left = lcaHelper(head.left, x, y);
    Treenode right = lcaHelper(head.right,x,y);

    if(left!=null && right!=null){
        return head;
    }
    return (left!=null) ? left:right;
}

public static int lca(Treenode head, int h1, int h2) {
    v1 = bfs(head,h1);
    v2 = bfs(head,h2);
    if(v1 && v2){
        Treenode lca = lcaHelper(head,h1,h2);
        return lca.value;
    }
    return -1;
}
}

Answer 24

Crude way:

• At every node
  • X = find if either of the n1, n2 exist on the left side of the Node
  • Y = find if either of the n1, n2 exist on the right side of the Node
    • if the node itself is n1 || n2, we can call it either found on left or right for the purposes of generalization.
  • If both X and Y is true, then the Node is the CA

The problem with the method above is that we will be doing the "find" multiple times, ie there is a possibility of each node getting traversed multiple times. We can overcome this problem if we can record the information so as to not process it again (think dynamic programming).

So rather than doing find every node, we keep a record of as to whats already been found.

Better Way:

• We check to see if for a given node if left_set (meaning either n1 | n2 has been found in the left subtree) or right_set in a depth first fashion. (NOTE: We are giving the root itself the property of being left_set if it is either n1 | n2)
• If both left_set and right_set then the node is a LCA.

Código:

struct Node *
findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) {
   int left_set, right_set;
   left_set = right_set = 0;
   struct Node *leftCA, *rightCA;
   leftCA = rightCA = NULL;

   if (root == NULL) {
      return NULL;
   }
   if (root == n1 || root == n2) {
      left_set = 1;
      if (n1 == n2) {
         right_set = 1;
      }
   }

   if(!left_set) {
      leftCA = findCA(root->left, n1, n2, &left_set);
      if (leftCA) {
         return leftCA;
      }
   }
   if (!right_set) {
      rightCA= findCA(root->right, n1, n2, &right_set);
      if(rightCA) {
         return rightCA;
      }
   }

   if (left_set && right_set) {
      return root;
   } else {
      *set = (left_set || right_set);
      return NULL;
   }
}

Answer 25

Some of the solutions here assumes that there is reference to the root node, some assumes that tree is a BST. Sharing my solution using hashmap, without reference to root node and tree can be BST or non-BST:

    var leftParent : Node? = left
    var rightParent : Node? = right
    var map = [data : Node?]()

    while leftParent != nil {
        map[(leftParent?.data)!] = leftParent
        leftParent = leftParent?.parent
    }

    while rightParent != nil {
        if let common = map[(rightParent?.data)!] {
            return common
        }
        rightParent = rightParent?.parent
    }

Answer 26

There can be one more approach. However it is not as efficient as the one already suggested in answers.

• Create a path vector for the node n1.

• Create a second path vector for the node n2.

• Path vector implying the set nodes from that one would traverse to reach the node in question.

• Compare both path vectors. The index where they mismatch, return the node at that index - 1. This would give the LCA.

Cons for this approach:

Need to traverse the tree twice for calculating the path vectors. Need addtional O(h) space to store path vectors.

However this is easy to implement and understand as well.

Code for calculating the path vector:

private boolean findPathVector (TreeNode treeNode, int key, int pathVector[], int index) {

        if (treeNode == null) {
            return false;
        }

        pathVector [index++] = treeNode.getKey ();

        if (treeNode.getKey () == key) {
            return true;
        }
        if (findPathVector (treeNode.getLeftChild (), key, pathVector, index) || 
            findPathVector (treeNode.getRightChild(), key, pathVector, index)) {

            return true;        
        }

        pathVector [--index] = 0;
        return false;       
    }

Answer 27

You are correct that without a parent node, solution with traversal will give you O(n) time complexity.

Traversal approach Suppose you are finding LCA for node A and B, the most straightforward approach is to first get the path from root to A and then get the path from root to B. Once you have these two paths, you can easily iterate over them and find the last common node, which is the lowest common ancestor of A and B.

Recursive solution Another approach is to use recursion. First, we can get LCA from both left tree and right tree (if exists). If the either of A or B is the root node, then the root is the LCA and we just return the root, which is the end point of the recursion. As we keep divide the tree into sub-trees, eventually, we''ll hit either A and B.

To combine sub-problem solutions, if LCA(left tree) returns a node, we know that both A and B locate in left tree and the returned node is the final result. If both LCA(left) and LCA(right) return non-empty nodes, it means A and B are in left and right tree respectively. In this case, the root node is the lowest common node.

Check Lowest Common Ancestor for detailed analysis and solution.

Answer 28

El código en Php. Supuse que el árbol es un árbol binario Array. Por lo tanto, ni siquiera necesita que el árbol calcule el LCA. input: índice de salida de dos nodos: índice de LCA

    <?php
 global $Ps;

function parents($l,$Ps)
{

    if($l % 2 ==0)
        $p = ($l-2)/2;
    else            
        $p = ($l-1)/2;

    array_push($Ps,$p);     
    if($p !=0)
        parents($p,$Ps);

    return $Ps; 
}
function lca($n,$m)
{
    $LCA = 0;
    $arr1 = array();
    $arr2 = array();
    unset($Ps); 
$Ps = array_fill(0,1,0);
    $arr1 = parents($n,$arr1);
    unset($Ps); 
$Ps = array_fill(0,1,0);
    $arr2 = parents($m,$arr2);

    if(count($arr1) > count($arr2))
        $limit = count($arr2);
    else
        $limit = count($arr1);

    for($i =0;$i<$limit;$i++)
    {
        if($arr1[$i] == $arr2[$i])
        {
            $LCA = $arr1[$i];
            break;
        }
    }
    return $LCA;//this is the index of the element in the tree

}

var_dump(lca(5,6));
?>

Dime si hay algún defecto.

Answer 29

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Answer 30

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        return left == null ? right : right == null ? left : root;
    }