Comment trouver le plus petit ancêtre commun de deux nœuds dans n'importe quel arbre binaire?

L'arbre binaire ici n'est pas nécessairement un arbre de recherche binaire.
La structure pourrait être considérée comme -

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

La solution maximale que je pourrais trouver avec un ami était quelque chose de ce genre -
Considérez cet arbre binaire :

La traversée en ordre donne - 8, 4, 9, 2, 5, 1, 6, 3, 7

Et la traversée post-ordre donne - 8, 9, 4, 5, 2, 6, 7, 3, 1

Ainsi, par exemple, si nous voulons trouver l'ancêtre commun des nœuds 8 et 5, alors nous faisons une liste de tous les nœuds qui sont entre 8 et 5 dans le parcours d'arbre inorder, qui dans ce cas se trouve être [4, 9 , 2]. Ensuite, nous vérifions quel nœud de cette liste apparaît en dernier dans le parcours de post-ordre, qui est 2. Par conséquent, l'ancêtre commun pour 8 et 5 est 2.

La complexité de cet algorithme, je crois, est O (n) (O (n) pour les traversées en ordre / post-ordre, le reste des étapes étant à nouveau O (n) car ce ne sont rien de plus que de simples itérations dans des tableaux). Mais il y a de fortes chances que ce soit faux. :-)

Mais c'est une approche très grossière, et je ne suis pas sûr si cela échoue dans certains cas. Existe-t-il une autre solution (peut-être plus optimale) à ce problème?

Nick Johnson a raison de dire qu'un algorithme de complexité en temps O (n) est le meilleur que vous puissiez faire si vous n'avez pas de pointeurs parents.) Pour une version récursive simple de cet algorithme, voir le code dans l'article de Kinding qui s'exécute en temps O (n) .

Mais gardez à l'esprit que si vos nœuds ont des pointeurs parents, un algorithme amélioré est possible. Pour les deux nœuds en question, construisez une liste contenant le chemin de la racine au nœud en commençant au nœud, puis en insérant le parent.

Donc, pour 8 dans votre exemple, vous obtenez (montrant les étapes): {4}, {2, 4}, {1, 2, 4}

Faites de même pour votre autre nœud en question, ce qui entraîne (étapes non illustrées): {1, 2}

Maintenant, comparez les deux listes que vous avez faites en recherchant le premier élément où la liste diffère, ou le dernier élément d'une des listes, selon la première éventualité.

Cet algorithme nécessite un temps O (h) où h est la hauteur de l'arbre. Dans le pire des cas, O (h) équivaut à O (n), mais si l'arbre est équilibré, c'est seulement O (log (n)). Il nécessite également un espace O (h). Une version améliorée est possible qui n'utilise que l'espace constant, avec le code affiché dans l' article du CEGRD

Indépendamment de la façon dont l'arbre est construit, s'il s'agit d'une opération que vous effectuez plusieurs fois sur l'arbre sans le changer entre les deux, il existe d'autres algorithmes que vous pouvez utiliser qui nécessitent une préparation de temps O (n) [linéaire], mais en trouvant ensuite paire ne prend que le temps O (1) [constant]. Pour obtenir des références à ces algorithmes, consultez la page sur les problèmes d'ancêtres communs les plus bas sur Wikipedia . (Merci à Jason d'avoir publié ce lien à l'origine)

En partant du rootnœud et en descendant si vous trouvez un nœud qui a l'un pou l' autre qcomme enfant direct, c'est l'ACV. (modifier - cela devrait être si pou qest la valeur du nœud, renvoyez-le. Sinon, cela échouera lorsque l'un de pou qest un enfant direct de l'autre.)

Sinon, si vous trouvez un nœud avec pdans son sous-arbre droit (ou gauche) et qdans son sous-arbre gauche (ou droit), il s'agit de l'ACV.

Le code fixe ressemble à:

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;
                }
        }
}

Le code ci-dessous échoue lorsque l'un est l'enfant direct de l'autre.

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;
                }
        }
}

Code en action

Voici le code de travail 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; 
}

Les réponses données jusqu'à présent utilisent la récursivité ou stockent, par exemple, un chemin en mémoire.

Ces deux approches peuvent échouer si vous avez un arbre très profond.

Voici mon point de vue sur cette question. Lorsque nous vérifions la profondeur (distance de la racine) des deux nœuds, s'ils sont égaux, nous pouvons alors remonter en toute sécurité des deux nœuds vers l'ancêtre commun. Si l'une des profondeurs est plus grande, nous devrions remonter du nœud le plus profond tout en restant dans l'autre.

Voici le code:

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 complexité temporelle de cet algorithme est: O (n). La complexité spatiale de cet algorithme est: O (1).

En ce qui concerne le calcul de la profondeur, nous pouvons d'abord nous souvenir de la définition: Si v est racine, profondeur (v) = 0; Sinon, profondeur (v) = profondeur (parent (v)) + 1. Nous pouvons calculer la profondeur comme suit:

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

Eh bien, cela dépend de la structure de votre arbre binaire. Vraisemblablement, vous avez un moyen de trouver le nœud feuille souhaité en fonction de la racine de l'arbre - appliquez-le simplement aux deux valeurs jusqu'à ce que les branches que vous choisissez divergent.

Si vous ne disposez pas d'un moyen de trouver la feuille souhaitée à partir de la racine, alors votre seule solution - à la fois en fonctionnement normal et pour trouver le dernier nœud commun - est une recherche par force brute de l'arbre.

Cela peut être trouvé à: - 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;
        }
    }
}

L'algorithme des ancêtres les moins communs hors ligne de Tarjan est assez bon (cf. aussi Wikipedia ). Il y a plus sur le problème (le plus petit problème d'ancêtre commun) sur Wikipedia .

Pour découvrir l'ancêtre commun de deux nœuds: -

• Trouvez le nœud donné Node1 dans l'arborescence à l'aide de la recherche binaire et enregistrez tous les nœuds visités dans ce processus dans un tableau, par exemple A1. Heure - O (logn), Espace - O (logn)
• Trouvez le Node2 donné dans l'arborescence à l'aide de la recherche binaire et enregistrez tous les nœuds visités dans ce processus dans un tableau, par exemple A2. Heure - O (logn), Espace - O (logn)
• Si la liste A1 ou la liste A2 est vide, alors un nœud n'existe pas donc il n'y a pas d'ancêtre commun.
• Si la liste A1 et la liste A2 ne sont pas vides, regardez dans la liste jusqu'à ce que vous trouviez un nœud non correspondant. Dès que vous trouvez un tel nœud, le nœud antérieur est un ancêtre commun.

Cela fonctionnerait pour l'arbre de recherche binaire.

J'ai fait une tentative avec des images illustratives et du code de travail en Java,

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

L'algorithme récursif ci-dessous fonctionnera en O (log N) pour un arbre binaire équilibré. Si l'un des nœuds passés dans la fonction getLCA () est le même que la racine, la racine sera l'ACV et il ne sera pas nécessaire d'effectuer une recussrion.

Cas de test. [1] Les deux nœuds n1 et n2 sont dans l'arborescence et résident de chaque côté de leur nœud parent. [2] Le nœud n1 ou n2 est la racine, le LCA est la racine. [3] Seul n1 ou n2 est dans l'arborescence, LCA sera soit le nœud racine du sous-arbre gauche de la racine de l'arbre, soit l'ACV sera le nœud racine du sous-arbre droit de la racine de l'arbre.

[4] Ni n1 ni n2 ne sont dans l'arborescence, il n'y a pas de LCA. [5] Les deux n1 et n2 sont en ligne droite l'un à côté de l'autre, LCA sera soit de n1 ou n2 qui se rapproche jamais de la racine de l'arbre.

//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);
}

Il suffit de descendre de l'arbre entier roottant que les deux nœuds donnés, disons pet q, pour lesquels l'ancêtre doit être trouvé, sont dans le même sous-arbre (ce qui signifie que leurs valeurs sont à la fois plus petites ou plus grandes que celles de racine).

Cela va directement de la racine à l'ancêtre le moins commun, sans regarder le reste de l'arbre, donc c'est à peu près aussi rapide que possible. Quelques façons de le faire.

Itératif, espace O (1)

Python

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 cas de débordement, je ferais (root.val - (long) p.val) * (root.val - (long) q.val)

Récursif

Python

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);
}

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
}

Considérez cet arbre

Si nous effectuons une traversée de post-ordre et de pré-ordre et trouvons le premier prédécesseur et successeur commun, nous obtenons l'ancêtre commun.

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

• par exemple: 1

Ancêtre le moins commun de 8,11

en postorder nous avons => 9,14,15,13,12,7 après 8 & 11 en précommande nous avons => 7,3,1,0,2,6,4,5,12,9 avant 8 & 11

9 est le premier nombre courant qui apparaît après 8 et 11 en post-commande et avant 8 et 11 en précommande, donc 9 est la réponse

• par exemple: 2

Ancêtre le moins commun de 5,10

11,9,14,15,13,12,7 en post-commande 7,3,1,0,2,6,4 en précommande

7 est le premier nombre qui apparaît après 5,10 en post-commande et avant 5,10 en précommande, donc 7 est la réponse

S'il s'agit d'un arbre binaire complet avec des enfants du nœud x comme 2 * x et 2 * x + 1, il existe un moyen plus rapide de le faire

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;  
}

Comment ça marche

1. obtenir les bits nécessaires pour représenter x & y qui en utilisant la recherche binaire est O (log (32))
2. le préfixe commun de la notation binaire de x & y est l'ancêtre commun
3. celui qui est représenté par le plus grand nombre de bits est amené au même bit par k >> diff
4. k = x ^ y efface le préfixe commun de x & y
5. trouver des bits représentant le suffixe restant
6. décalez x ou y par bits de suffixe pour obtenir le préfixe commun qui est l'ancêtre commun.

Cela fonctionne parce que fondamentalement, divisez le plus grand nombre par deux récursivement jusqu'à ce que les deux nombres soient égaux. Ce nombre est l'ancêtre commun. La division est effectivement la bonne opération de changement de vitesse. Nous devons donc trouver le préfixe commun de deux nombres pour trouver l'ancêtre le plus proche

Dans scala, vous pouvez:

  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
    }
  }

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;
    }

Voici la manière C ++ de le faire. J'ai essayé de garder l'algorithme aussi simple que possible à comprendre:

// 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;
  }
};

Comment l'utiliser:

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

Le moyen le plus simple de trouver l'ancêtre commun le plus bas consiste à utiliser l'algorithme suivant:

Examiner le nœud racine

si valeur1 et valeur2 sont strictement inférieures à la valeur au nœud racine 
    Examiner le sous-arbre gauche
sinon si valeur1 et valeur2 sont strictement supérieures à la valeur au nœud racine 
    Examiner le sous-arbre droit
autre
    retourner la racine

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;
} 

J'ai trouvé une solution

1. Prendre en ordre
2. Prenez la précommande
3. Prendre la commande

En fonction de 3 parcours, vous pouvez décider qui est le LCA. À partir de LCA, trouvez la distance des deux nœuds. Ajoutez ces deux distances, qui est la réponse.

Voici ce que je pense,

1. Trouvez l'itinéraire pour le premier nœud, enregistrez-le sur arr1.
2. Commencez à trouver l'itinéraire pour le nœud 2, tout en vérifiant chaque valeur de la racine à arr1.
3. moment où la valeur diffère, quittez. L'ancienne valeur correspondante est l'ACV.

Complexité: étape 1: O (n), étape 2 = ~ O (n), total = ~ O (n).

Voici deux approches en c # (.net) (toutes deux discutées ci-dessus) pour référence:

1. Version récursive de la recherche de LCA dans l'arbre binaire (O (N) - car au plus chaque nœud est visité) (les principaux points de la solution est LCA est (a) le seul nœud de l'arbre binaire où les deux éléments résident de chaque côté des sous-arbres (à gauche et à droite) est LCA. (b) Et aussi peu importe quel nœud est présent de chaque côté - au départ j'ai essayé de garder cette information, et évidemment la fonction récursive est devenue si déroutante.Une fois que je l'ai réalisée, elle est devenue très élégante.

2. La recherche des deux nœuds (O (N)) et le suivi des chemins (utilise de l'espace supplémentaire - donc, # 1 est probablement supérieur même si l'espace est probablement négligeable si l'arbre binaire est bien équilibré, car la consommation de mémoire supplémentaire sera juste en O (log (N)).

   de sorte que les chemins sont comparés (essentiellement similaire à la réponse acceptée - mais les chemins sont calculés en supposant que le nœud de pointeur n'est pas présent dans le nœud de l'arbre binaire)

3. Juste pour compléter ( sans rapport avec la question ), LCA en BST (O (log (N))

4. Des tests

Récursif:

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;
        }

où ci-dessus la version récursive privée est appelée par la méthode publique suivante:

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;
        }

Solution en gardant une trace des chemins des deux nœuds:

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;
        }

où FindNodeAndPath est défini comme

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) - non lié (juste pour compléter pour référence)

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;
        }

Tests unitaires

[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);
            }
        }

Si quelqu'un s'intéresse au pseudo code (pour les travaux universitaires à domicile), en voici un.

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

Bien que cela ait déjà été répondu, c'est mon approche de ce problème en utilisant le langage de programmation C. Bien que le code montre un arbre de recherche binaire (en ce qui concerne insert ()), mais l'algorithme fonctionne également pour un arbre binaire. L'idée est de passer en revue tous les nœuds qui se trouvent du nœud A au nœud B dans un parcours en ordre, de rechercher les indices pour ceux-ci dans le parcours de post-ordre. Le nœud avec l'index maximum dans le parcours post-ordre est le plus petit ancêtre commun.

Il s'agit d'un code C fonctionnel pour implémenter une fonction pour trouver le plus petit ancêtre commun dans un arbre binaire. Je propose également toutes les fonctions utilitaires, etc., mais passez à CommonAncestor () pour une compréhension rapide.

#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);


}

Il peut y avoir une autre approche. Cependant, il n'est pas aussi efficace que celui déjà suggéré dans les réponses.

• Créez un vecteur de chemin pour le nœud n1.

• Créez un deuxième vecteur de chemin pour le nœud n2.

• Vecteur de chemin impliquant l'ensemble des nœuds de celui-ci traverser pour atteindre le nœud en question.

• Comparez les deux vecteurs de chemin. L'index où ils ne correspondent pas, retourne le nœud à cet index - 1. Cela donnerait l'ACV.

Inconvénients de cette approche:

Besoin de parcourir l'arbre deux fois pour calculer les vecteurs de chemin. Besoin d'espace O (h) supplémentaire pour stocker les vecteurs de chemin.

Cependant, cela est également facile à mettre en œuvre et à comprendre.

Code de calcul du vecteur de chemin:

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;       
    }

Essayez comme ça

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;
}

Manière brute:

• À chaque nœud
  • X = trouver si l'un des n1, n2 existe sur le côté gauche du nœud
  • Y = trouver si l'un des n1, n2 existe sur le côté droit du nœud
    • si le nœud lui-même est n1 || n2, nous pouvons l'appeler trouvé à gauche ou à droite à des fins de généralisation.
  • Si X et Y sont tous les deux vrais, alors le nœud est l'autorité de certification

Le problème avec la méthode ci-dessus est que nous allons faire la "recherche" plusieurs fois, c'est-à-dire qu'il y a une possibilité que chaque nœud soit traversé plusieurs fois. Nous pouvons surmonter ce problème si nous pouvons enregistrer les informations afin de ne pas les traiter à nouveau (pensez à la programmation dynamique).

Ainsi, plutôt que de rechercher chaque nœud, nous gardons une trace de ce qui a déjà été trouvé.

Meilleure façon:

• Nous vérifions si pour un nœud donné si left_set (ce qui signifie que n1 | n2 a été trouvé dans le sous-arbre de gauche) ou right_set en profondeur d'abord. (NOTE: Nous donnons à la racine elle-même la propriété d'être left_set si c'est soit n1 | n2)
• Si à la fois left_set et right_set, le nœud est un LCA.

Code:

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;
   }
}

Code pour A Breadth First Search pour vous assurer que les deux nœuds sont dans l'arborescence. Alors seulement, avancez avec la recherche LCA. Veuillez commenter si vous avez des suggestions à améliorer. Je pense que nous pouvons probablement les marquer comme visités et redémarrer la recherche à un certain point où nous nous sommes arrêtés pour améliorer le deuxième nœud (s'il n'est pas trouvé VISITÉ)

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;
}
}

Vous avez raison de dire que sans nœud parent, une solution avec traversée vous donnera une complexité en temps O (n).

Approche transversale transversale Supposons que vous trouviez l'ACV pour les nœuds A et B, l'approche la plus simple consiste d'abord à obtenir le chemin de la racine à A, puis à obtenir le chemin de la racine à B.Une fois que vous avez ces deux chemins, vous pouvez facilement les parcourir. et trouvez le dernier nœud commun, qui est le plus petit ancêtre commun de A et B.

Solution récursive Une autre approche consiste à utiliser la récursivité. Tout d'abord, nous pouvons obtenir LCA à la fois de l'arbre gauche et de l'arbre droit (s'il existe). Si l'un de A ou B est le nœud racine, alors la racine est l'ACV et nous renvoyons simplement la racine, qui est le point final de la récursivité. Au fur et à mesure que nous divisons l'arbre en sous-arbres, nous atteindrons finalement A et B.

Pour combiner des solutions de sous-problèmes, si LCA (arbre de gauche) renvoie un nœud, nous savons que A et B se situent dans l'arbre de gauche et le nœud retourné est le résultat final. Si LCA (gauche) et LCA (droite) renvoient des nœuds non vides, cela signifie que A et B sont respectivement dans l'arborescence gauche et droite. Dans ce cas, le nœud racine est le nœud commun le plus bas.

Vérifiez le plus petit ancêtre commun pour une analyse détaillée et une solution.

Certaines des solutions ici supposent qu'il existe une référence au nœud racine, d'autres supposent que l'arbre est un BST. Partager ma solution en utilisant hashmap, sans référence au rootnœud et à l'arborescence peut être BST ou 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
    }

Solution 1: récursif - plus rapide

• L'idée est de parcourir l'arbre à partir de la racine. Si l'une des clés p et q données correspond à root, alors root est LCA, en supposant que les deux clés sont présentes. Si root ne correspond à aucune des clés, nous recurse pour le sous-arbre gauche et droit.
• Le nœud qui a une clé présente dans son sous-arbre gauche et l'autre clé présente dans le sous-arbre droit est le LCA. Si les deux clés se trouvent dans le sous-arbre gauche, alors le sous-arbre gauche a également LCA, sinon LCA se trouve dans le sous-arbre droit.

• Complexité temporelle: O (n)
• Complexité spatiale: O (h) - pour la pile d'appels récursifs

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)
    }
}

Solution 2: Itérative - Utilisation des pointeurs parents - Plus lente

• Créez une table de hachage vide.
• Insérez p et tous ses ancêtres dans la table de hachage.
• Vérifiez si q ou l'un de ses ancêtres existe dans la table de hachage, si oui, retournez le premier ancêtre existant.

• Complexité temporelle: O (n) - Dans le pire des cas, nous pourrions visiter tous les nœuds de l'arbre binaire.
• Complexité de l'espace: O (n) - L'espace utilisé le pointeur parent Hash-table, ancestor_set et queue, serait O (n) chacun.

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;
    }
}