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

187

El árbol binario aquí puede no ser necesariamente un árbol de búsqueda binaria.
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í:
considere este árbol binario :

Árbol binario

El rendimiento transversal del pedido: 8, 4, 9, 2, 5, 1, 6, 3, 7

Y los rendimientos transversales 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, entonces hacemos una lista de todos los nodos que están entre 8 y 5 en el recorrido del árbol de pedidos, 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. Por lo tanto, el ancestro común para 8 y 5 es 2.

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

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

Siddhant
fuente
66
Por curiosidad, ¿cuál es el uso práctico de esto?
David Brunelle
19
@David: la respuesta de consultas LCA es bastante útil. Árbol de sufijo LCA + = algoritmos potentes relacionados con cadenas.
44
Y cuando hice una pregunta similar, fue rechazada con comentarios como su pregunta de entrevista. ¿Dualidad de SO? :(
some_other_guy
55
@Siddant +1 para los detalles dados en la pregunta. :)
amod
55
@DavidBrunelle Una aplicación práctica de computación del LCA: es un cálculo esencial cuando se procesan páginas web, específicamente cuando se computan las Hojas de Estilo en Cascada (CSS) que son aplicables a un elemento DOM particular.
zc22

Respuestas:

74

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 principales.) Para una versión recursiva simple de ese algoritmo, vea el código en la publicación de Kinding que se ejecuta en tiempo O (n) .

Pero tenga en cuenta que si sus nodos tienen punteros principales, es posible un algoritmo mejorado. Para ambos nodos en cuestión, construya una lista que contenga la ruta desde la raíz hasta el nodo comenzando en el nodo e insertando el padre por delante.

Entonces, para 8 en su ejemplo, obtiene (mostrando pasos): {4}, {2, 4}, {1, 2, 4}

Haga lo mismo para su otro nodo en cuestión, resultando en (pasos no mostrados): {1, 2}

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

Este algoritmo requiere un tiempo O (h) 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 espacio O (h). Es posible una versión mejorada que use solo espacio constante, con el código mostrado en la publicación de CEGRD


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

Kevin Cathcart
fuente
1
Eso hace el trabajo si se da el puntero principal. Los nodos en el árbol son como la estructura que di en mi pregunta: solo los punteros secundarios izquierdo / derecho, sin puntero principal. ¿Hay alguna solución O (log (n)) si no hay un puntero principal disponible, y el árbol no es un árbol de búsqueda binario, y es solo un árbol binario?
Siddhant
2
Si no tiene una forma particular de encontrar la ruta entre el padre y un nodo dado, entonces tomará O (n) tiempo en promedio para encontrarlo. Eso hará que sea imposible tener tiempo O (log (n)). Sin embargo, el costo O (n) de una sola vez, con O (1) encontrar pares puede ser su mejor opción de todos modos si fuera a realizar esta operación muchas veces sin cambiar el árbol en el medio. De lo contrario, si es posible, debe agregar el puntero principal. Puede hacer que algunos algoritmos potenciales sean más rápidos, pero estoy bastante seguro de que no cambia el orden de ningún algoritmo existente. Espero que esto ayude.
Kevin Cathcart el
1
este enfoque se puede hacer usando la memoria O (1) - vea la solución de Artelius (y otros) en stackoverflow.com/questions/1594061/…
Tom Sirgedas
@Tom: De hecho, eso funcionaría para limitar la complejidad de la memoria a O (1) para el algoritmo basado en listas. Obviamente, eso significa iterar a través del árbol una vez por cada lado para obtener las profundidades de los nodos, y luego una segunda vez (parcial) para encontrar el ancestro común. O (h) tiempo y O (1) espacio es claramente óptimo para el caso de tener punteros principales, y no hacer precomputación de O (n).
Kevin Cathcart
1
@ALBI O(h)es solo O(log(n))si el árbol está equilibrado. Para cualquier árbol, ya sea binario o no, si tiene punteros principales, puede determinar la ruta de una hoja a la raíz a O(h)tiempo, simplemente siguiendo el puntero principal hasta el hmomento. Eso te da el camino desde la hoja hasta la raíz. Si las rutas se almacenan como una pila, al iterar la pila se obtiene la ruta desde la raíz hasta la hoja. Si carece de punteros principales y no tiene una estructura especial para el árbol, encontrar el camino desde la raíz hasta la hoja lleva O(n)tiempo.
Kevin Cathcart
108

Comenzando desde el rootnodo y moviéndose hacia abajo si encuentra algún nodo que tenga uno po qcomo su hijo directo, entonces es el LCA. (edit - esto debería ser si po qes el valor del nodo, devuélvalo De lo contrario, se producirá un error cuando uno de. po qes un hijo directo de la otra.)

De lo contrario, si encuentra un nodo con psu subárbol derecho (o izquierdo) y qsu 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 siguiente código 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

codictorio
fuente
2
solución elegante, pero la raíz == p || root == q => return bit de raíz parece demasiado optimista. ¿Qué sucede si la raíz es p / q, pero el otro nodo buscado no está realmente en el árbol?
Ian Durkan
15
Supongo que este código falla cuando p o q es un valor que no está en el árbol binario. Estoy en lo cierto? Por ejemplo, LCA (8,20). su código devuelve 8. pero 20 no está presente en el árbol binario
javaMan
3
¿Cuál es el costo de esta solución? ¿Es eficiente? Parece continuar buscando incluso después de haber encontrado p y q. ¿Se debe a la posibilidad de que pyq no sean únicos en el árbol ya que no es un BST y puede contener duplicados?
MikeB
3
@MikeB, esta solución es definitivamente O (n), porque atraviesas cada nodo solo una vez en el peor de los casos. Peter Lee, este es el más eficiente que puedes lograr sin usar punteros de padres. ¿Tienes una mejor solución?
gsingh2011
8
la primera solución imperfecta debe eliminarse para que no distraiga
Zinan Xing
50

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; 
}
Akash Verma
fuente
44
Esto no funciona cuando un nodo no existe en el árbol.
Pratik Khadloya
¿optimizarías tu código si el árbol dado es un BST?
Mona Jalal
1
"Si la raíz es una de aob, entonces es el LCA". Esto podría no ser cierto. Lo que sabe en este momento es que no necesita verificar a ninguno de sus hijos para encontrar el LCA. Esto sucede porque luego podemos verificar si para el padre de la raíz, hubo coincidencias en ambas ramas (LCA es padre) o solo una de ellas (en cuyo caso, ese podría ser el LCA, o un ancestro aún mayor podría ser el LCA )
andresp
28

Las respuestas dadas hasta ahora usan recursividad o almacena, por ejemplo, una ruta en la memoria.

Ambos enfoques pueden fallar si tiene 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, entonces podemos movernos con seguridad hacia arriba desde ambos nodos hacia el ancestro común. Si una de las profundidades es más grande, entonces debemos movernos hacia arriba desde el nodo más profundo mientras permanecemos en el otro.

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 temporal de este algoritmo es: O (n). La complejidad espacial 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, profundidad (v) = profundidad (padre (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;
CEGRD
fuente
66
Los árboles binarios no tienen una referencia al elemento padre, por lo general. Agregar una referencia principal se puede hacer sin ningún problema, pero consideraría que O (n) espacio auxiliar.
John Kurlak
Hay una suposición sutil en esta solución. Si un nodo es un padre directo o indirecto del otro (es decir, el nodo más profundo está en un árbol enraizado en el nodo menos profundo), esta solución devuelve el padre del nodo menos profundo como resultado. Dependiendo de cómo defina el ancestro común más bajo, esto puede no ser lo que desea. Algunas definiciones requerirán que el nodo menos profundo sea el padre. En este caso, necesitaría rastrear cuál es el nodo menos profundo y devolverlo.
Srikanth
8

Bueno, este tipo de depende de cómo está estructurado su á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 una manera de encontrar la hoja deseada dada 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 del árbol.

Nick Johnson
fuente
8

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;
        }
    }
}
Baban
fuente
¿podría decirme cómo se comportará su código si p está presente pero q no está presente en el árbol? Del mismo modo, p y q no están presentes. ¡¡¡Gracias!!!
Intentando
¿Cuál es la gran O en términos de tiempo? Creo que es O (n * log (n)), dos lentos.
Peter Lee
6

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

  • Encuentre el nodo dado Nodo1 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 utilizando 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á vacía, entonces el nodo no existe, por lo que no hay un ancestro común.
  • Si la lista A1 y la lista A2 no están vacías, busque en la lista hasta que encuentre un nodo que no coincida. Tan pronto como encuentre dicho nodo, el nodo anterior es un ancestro común.

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

Vipin
fuente
2
Declaró claramente que el árbol NO es necesariamente un BST.
Peter Lee
@Peter Lee: la lógica anterior funcionaría incluso para cualquier árbol binario con un simple cambio. En lugar de la búsqueda binaria de nodos dados, aplique la búsqueda lineal (es decir, cualquier recorrido pero debería ser el mismo para ambos casos). Por supuesto, el tiempo de ejecución sería O (n) en lugar de O (logn). De hecho, este algo es el más robusto cuando el puntero principal no está disponible. El algoritmo rucursivo dado por muchos (a saber, 'codaddict') no funcionará cuando uno de los nodos dados no pertenezca al árbol)
KGhatak
3

El siguiente algoritmo recursivo 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 la raíz, entonces la raíz será el LCA y no habrá necesidad de realizar ninguna recusación.

Casos de prueba. [1] Ambos nodos n1 y n2 están en el árbol y residen a ambos lados 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 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á de n1 o n2 que alguna vez esté 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);
}
gilla07
fuente
3

Simplemente baje de todo el árbol rootsiempre que ambos nodos dados, digamos pyq , para los cuales se debe encontrar Ancestor, se encuentren en el mismo subárbol (lo que significa que sus valores son más pequeños o más grandes que los de la raíz).

Esto camina directamente desde la raíz hasta el Ancestro Menos Común, sin mirar el resto del árbol, por lo que es casi tan rápido como puede. 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, 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);
}
Rajnish
fuente
2
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
}
Krishnachandra Sharma
fuente
2

Considera este árbol ingrese la descripción de la imagen aquí

Si hacemos un recorrido de postorder y preorder y encontramos el primer predecesor y sucesor común que ocurre, 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

  • por ejemplo: 1

Antepasado mínimo común de 8,11

en postorder tenemos => 9,14,15,13,12,7 después de 8 y 11 en preorden 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 preorder, por lo tanto 9 es la respuesta

  • por ejemplo: 2

Antepasado mínimo común 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 preorder, por lo tanto, 7 es la respuesta

nnc
fuente
2

Si es un árbol binario completo con hijos del nodo x como 2 * x y 2 * x + 1, entonces 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. obtener bits necesarios para representar x & y que mediante la búsqueda binaria es O (log (32))
  2. el prefijo común de notación binaria de x & 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 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 entre dos recursivamente hasta que ambos números sean iguales. Ese número es el ancestro común. Dividir es efectivamente la operación de turno correcta. Entonces necesitamos encontrar el prefijo común de dos números para encontrar el antepasado más cercano

hacker codificador
fuente
2

En scala, puedes:

  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
    }
  }
Jatin
fuente
1
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;
    }
Cabeza y cola
fuente
0

Aquí está la forma C ++ de hacerlo. Intenté mantener el algoritmo lo más fácil posible de entender:

// 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)
  ...
iammilind
fuente
0

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

Examinar nodo raíz

si valor1 y valor2 son estrictamente menores que el valor en el nodo raíz 
    Examinar subárbol izquierdo
de lo contrario, si value1 y value2 son estrictamente mayores que el valor en el nodo raíz 
    Examinar subárbol derecho
más
    raíz de retorno
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;
} 
usuario2182531
fuente
66
¡NO es un BST!
Peter Lee
0

Encontre una solucion

  1. Tomar orden
  2. Toma preordenar
  3. Tomar postorder

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

Rajdeep Sardar
fuente
0

Esto es lo que pienso.

  1. Encuentre la ruta para el nodo de puño, guárdelo en arr1.
  2. Comience a encontrar la ruta para el nodo 2, mientras lo hace, verifique cada valor desde la raíz hasta arr1.
  3. momento en que el valor difiere, salir. El antiguo valor coincidente es el LCA.

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

badri.coder
fuente
0

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

  1. Versión recursiva de encontrar LCA en árbol binario (O (N), ya que como máximo se visita cada nodo) (los puntos principales de la solución es que LCA es (a) único nodo en árbol binario donde ambos elementos residen a ambos lados de los subárboles (izquierda y derecha) es LCA. (b) Y tampoco importa qué nodo esté presente en ambos lados: inicialmente intenté 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. Buscar ambos nodos (O (N)) y realizar un seguimiento de las rutas (usa espacio adicional, por lo tanto, el n. ° 1 es probablemente superior, incluso aunque el espacio sea insignificante si el árbol binario está bien equilibrado, ya que el consumo de memoria adicional será solo en O (log (N)).

    para que las rutas se comparen (esencialmente similar a la respuesta aceptada, pero las rutas se calculan asumiendo 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 la versión recursiva privada anterior se invoca 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 haciendo 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 completar 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);
            }
        }
Soñador
fuente
0

Si alguien interesado en pseudocódigo (para trabajos en el hogar universitario) 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
Sameera R.
fuente
0

Aunque esto ya ha sido respondido, este es mi enfoque para este problema usando el lenguaje de programación C. Aunque el código muestra un árbol de búsqueda binario (en lo que respecta a insert ()), el algoritmo también funciona para un árbol binario. La idea es repasar todos los nodos que se encuentran desde el nodo A al nodo B en el recorrido transversal, buscar los índices para estos en el recorrido del orden posterior. El nodo con el índice máximo en el recorrido de orden posterior 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 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);


}
SeattleOrBayArea
fuente
0

Puede haber un enfoque más. Sin embargo, no es tan eficiente como el que ya se sugirió en las respuestas.

  • Cree un vector de ruta para el nodo n1.

  • Cree un segundo vector de ruta para el nodo n2.

  • El vector de ruta implica que los nodos establecidos desde ese atravesarían para alcanzar el nodo en cuestión.

  • Compara ambos vectores de ruta. El índice donde no coinciden, devuelve el nodo en ese índice - 1. Esto daría el LCA.

Contras para este enfoque:

Necesita atravesar el árbol dos veces para calcular los vectores de ruta. Necesita espacio adicional O (h) para almacenar vectores de ruta.

Sin embargo, esto también es fácil de implementar y comprender.

Código para calcular el vector de ruta:

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;       
    }
Sumit Trehan
fuente
0

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;
}
shubhamv
fuente
0

Forma cruda:

  • En cada nodo
    • X = encontrar si alguno de los n1, n2 existe en el lado izquierdo del nodo
    • Y = buscar si alguno de los n1, n2 existe en el lado derecho del nodo
      • si el nodo en sí es n1 || n2, podemos llamarlo encontrado a la izquierda o a la derecha para fines de generalización.
    • Si tanto X como Y son verdaderas, entonces el Nodo es la CA

El problema con el método anterior es que haremos el "hallazgo" varias veces, es decir, existe la posibilidad de que cada nodo sea atravesado varias veces. Podemos superar este problema si podemos registrar la información para no procesarla nuevamente (piense en la programación dinámica).

Entonces, en lugar de buscar cada nodo, mantenemos un registro de lo que ya se ha encontrado.

Mejor manera:

  • Verificamos si para un nodo dado si left_set (lo que significa que n1 | n2 se ha encontrado en el subárbol izquierdo) o right_set en profundidad en primer lugar. (NOTA: Le estamos dando a la raíz la propiedad de ser left_set si es n1 | n2)
  • Si ambos, left_set y right_set, el nodo es un 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;
   }
}
Shatru Sadhu
fuente
0

Código para A Breadth First Search para asegurarse de que ambos nodos estén en el árbol. Solo entonces avance con la búsqueda de LCA. Comente si tiene alguna sugerencia para mejorar. Creo que probablemente podamos marcarlos como visitados y reiniciar la búsqueda en un punto determinado donde lo dejamos para mejorar para el segundo nodo (si no se encuentra VISITADO)

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;
}
}
Neelesh Salian
fuente
0

Tiene razón en que sin un nodo principal, la solución con recorrido le dará O (n) complejidad de tiempo.

Enfoque transversal Suponga que está encontrando LCA para los nodos A y B, el enfoque más directo es obtener primero la ruta de la raíz a A y luego obtener la ruta de la raíz a B. Una vez que tenga estas dos rutas, puede iterar fácilmente sobre ellas. y encuentre el último nodo común, que es el ancestro común más bajo de A y B.

Solución recursiva Otro enfoque es utilizar la recursividad. Primero, podemos obtener LCA tanto del árbol izquierdo como del árbol derecho (si existe). Si A o B es el nodo raíz, entonces la raíz es el LCA y simplemente devolvemos la raíz, que es el punto final de la recursión. A medida que sigamos dividiendo el árbol en subárboles, eventualmente golpearemos A y B.

Para combinar soluciones de subproblemas, si LCA (árbol izquierdo) devuelve un nodo, sabemos que tanto A como B se ubican en el árbol izquierdo y el nodo devuelto es el resultado final. Si tanto LCA (izquierda) como LCA (derecha) devuelven nodos no vacíos, significa que A y B están en el árbol izquierdo y derecho respectivamente. En este caso, el nodo raíz es el nodo común más bajo.

Verifique el Ancestro común más bajo para obtener un análisis detallado y una solución.

marca
fuente
0

Algunas de las soluciones aquí asumen que hay referencia al nodo raíz, algunas asumen que el árbol es un BST. Compartir mi solución usando hashmap, sin referencia al rootnodo y al árbol puede ser BST o no 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
    }
janusfidel
fuente
0

Solución 1: Recursivo - Más rápido

  • La idea es atravesar el árbol a partir de la raíz. Si alguna de las claves dadas p y q coincide con la raíz, entonces la raíz es LCA, suponiendo que ambas claves estén presentes. Si la raíz no coincide con ninguna de las claves, recurrimos para el subárbol izquierdo y derecho.
  • El nodo que tiene una clave presente en su subárbol izquierdo y la otra clave presente en el subárbol derecho es el LCA. Si ambas teclas se encuentran en el subárbol izquierdo, entonces el subárbol izquierdo también tiene LCA; de lo contrario, LCA se encuentra en el subárbol derecho.
  • Complejidad de tiempo: O (n)
  • Complejidad espacial: O (h) - para la pila de llamadas recursivas
class Solution 
{
    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);

        if(left == null)
            return right;
        else if(right == null)
            return left;
        else
            return root;    // If(left != null && right != null)
    }
}

Solución 2: Iterativo - Uso de punteros principales - Más lento

  • Crea una tabla hash vacía.
  • Inserte p y todos sus antepasados ​​en la tabla hash.
  • Compruebe si q o alguno de sus antepasados ​​existen en la tabla hash, en caso afirmativo, devuelva el primer antepasado existente.
  • Complejidad de tiempo: O (n): en el peor de los casos, podríamos estar visitando todos los nodos del árbol binario.
  • Complejidad del espacio: O (n): el espacio utilizaba el puntero principal Hash-table, ancestor_set y queue, serían O (n) cada uno.
class Solution
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
        HashSet<TreeNode> ancestors_set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();

        parent_map.put(root, null);
        queue.add(root);

        while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
        {
            TreeNode node = queue.poll();

            if(node.left != null)
            {
                parent_map.put(node.left, node);
                queue.add(node.left);
            }
            if(node.right != null)
            {
                parent_map.put(node.right, node);
                queue.add(node.right);
            }
        }

        while(p != null)
        {
            ancestors_set.add(p);
            p = parent_map.get(p);
        }

        while(!ancestors_set.contains(q))
            q = parent_map.get(q);

        return q;
    }
}
Pratik Patil
fuente