Como encontrar o menor ancestral comum de dois nós em qualquer árvore binária?

187

A Árvore Binária aqui pode não ser necessariamente uma Árvore de Pesquisa Binária.
A estrutura pode ser tomada como -

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

A solução máxima que eu consegui encontrar com um amigo foi algo desse tipo -
considere esta árvore binária :

Árvore binária

O percurso transversal da ordem produz - 8, 4, 9, 2, 5, 1, 6, 3, 7

E a passagem pós-ordem produz - 8, 9, 4, 5, 2, 6, 7, 3, 1

Por exemplo, se queremos encontrar o ancestral comum dos nós 8 e 5, fazemos uma lista de todos os nós que estão entre 8 e 5 na travessia da árvore de ordem de entrada, que neste caso é [4, 9 2] Em seguida, verificamos qual nó nesta lista aparece por último no percurso da ordem posterior, que é 2. Portanto, o ancestral comum de 8 e 5 é 2.

A complexidade desse algoritmo, creio, é O (n) (O (n) para travessias dentro / fora da ordem, o restante das etapas sendo novamente O (n), pois elas nada mais são do que simples iterações em matrizes). Mas há uma forte chance de que isso esteja errado. :-)

Mas essa é uma abordagem muito grosseira, e não tenho certeza se ela se quebra em alguns casos. Existe alguma outra solução (possivelmente mais ideal) para esse problema?

Siddhant
fonte
6
Por curiosidade, qual é a utilidade prática disso?
David Brunelle
19
@ David: A resposta à consulta LCA é bastante útil. Árvore LCA + Suffix = poderosos algoritmos relacionados a strings.
44
E quando eu fiz uma pergunta semelhante, ela foi rejeitada com comentários como a pergunta da entrevista. Dualidade de SO? :(
some_other_guy
5
@Siddant +1 para os detalhes fornecidos na pergunta. :)
AMOD
5
@DavidBrunelle Uma aplicação prática de computação da LCA: é um cálculo essencial ao renderizar páginas da Web, especificamente ao calcular as CSS (Cascading Style Sheets) aplicáveis ​​a um elemento DOM em particular.
Zc22 7/06

Respostas:

74

Nick Johnson está certo de que um algoritmo de complexidade de tempo O (n) é o melhor que você pode fazer se não tiver ponteiros pai.) Para uma versão recursiva simples desse algoritmo, veja o código na publicação de Kinding, que é executada em tempo O (n) .

Mas lembre-se de que, se seus nós tiverem ponteiros pai, um algoritmo aprimorado será possível. Para os dois nós em questão, construa uma lista contendo o caminho da raiz para o nó, iniciando no nó e inserindo o pai com uma frente.

Portanto, no exemplo 8, você obtém (mostrando as etapas): {4}, {2, 4}, {1, 2, 4}

Faça o mesmo para o outro nó em questão, resultando em (etapas não mostradas): {1, 2}

Agora compare as duas listas criadas procurando o primeiro elemento em que a lista difere ou o último elemento de uma das listas, o que ocorrer primeiro.

Este algoritmo requer tempo O (h) em que h é a altura da árvore. No pior caso, O (h) é equivalente a O (n), mas se a árvore estiver equilibrada, isso é apenas O (log (n)). Também requer espaço O (h). É possível uma versão aprimorada que utilize apenas espaço constante, com o código mostrado no post do CEGRD


Independentemente de como a árvore é construída, se esta for uma operação que você executa muitas vezes na árvore sem alterá-la, existem outros algoritmos que você pode usar que requerem preparação do tempo O (n) [linear], mas depois encontram qualquer par leva apenas tempo O (1) [constante]. Para referências a esses algoritmos, consulte a página com problemas mais baixos de ancestrais comuns na Wikipedia . (Agradecemos a Jason por postar originalmente este link)

Kevin Cathcart
fonte
1
Isso faz o trabalho se o ponteiro pai for fornecido. Os nós na árvore são como a estrutura que dei na minha pergunta - apenas os ponteiros filhos esquerdo / direito, nenhum ponteiro pai. Existe alguma solução O (log (n)) se não houver um ponteiro pai disponível e a árvore não for uma árvore de pesquisa binária e for apenas uma árvore binária?
Siddhant
2
Se você não tiver uma maneira específica de encontrar o caminho entre o pai e um nó, levará O (n) tempo, em média, para encontrá-lo. Isso tornará impossível ter tempo O (log (n)). No entanto, o custo único de O (n), com a descoberta do par de O (1), pode ser sua melhor aposta se você realizar essa operação muitas vezes sem alterar a árvore no meio. Caso contrário, se possível, adicione o ponteiro pai. Ele pode tornar alguns algoritmos em potencial mais rápidos, mas tenho certeza de que não altera a ordem de nenhum algoritmo existente. Espero que isto ajude.
9117 Kevin Cathcart
1
esta abordagem pode ser feito usando a memória O (1) - ver Artelius (e outros) solução a stackoverflow.com/questions/1594061/...
Tom Sirgedas
@ Tom: De fato, isso funcionaria para limitar a complexidade da memória a O (1) para o algoritmo baseado em lista. Obviamente, isso significa percorrer a própria árvore uma vez uma vez para cada lado para obter as profundidades dos nós e, em seguida, uma segunda vez (parcial) para encontrar o ancestral comum. O (h) tempo e O (1) espaço são claramente ótimos para o caso de ponteiros pai e não realizar pré-computação em O (n).
Kevin Cathcart
1
O @ALBI O(h)é apenas O(log(n))se a árvore estiver equilibrada. Para qualquer árvore, seja binária ou não, se você tiver ponteiros pai, poderá determinar o caminho de uma folha para a raiz no O(h)tempo, simplesmente seguindo o ponteiro pai várias hvezes. Isso fornece o caminho da folha para a raiz. Se os caminhos forem armazenados como uma pilha, a iteração da pilha fornecerá o caminho da raiz para a folha. Se você não possui ponteiros pai e não possui uma estrutura especial para a árvore, encontrar o caminho da raiz para a folha leva O(n)tempo.
precisa
108

Iniciando a partir do rootnó e movendo-se para baixo, se você encontrar algum nó que tenha pou qcomo filho direto, é o LCA. (editar - este deve ser se pou qfor o valor do nó, retorne-o. Caso contrário, falhará quando um de pou qfor um filho direto do outro.)

Caso pcontrário, se você encontrar um nó na subárvore direita (ou esquerda) e qna subárvore esquerda (ou direita), será o LCA.

O código fixo se parece com:

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

O código abaixo falha quando um deles é filho direto de outro.

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 em ação

codaddict
fonte
2
solução elegante, mas a raiz == p || root == q => retornar bit raiz parece super-otimista. E se a raiz for p / q, mas o outro nó procurado não estiver na árvore?
precisa
15
Eu acho que esse código falha quando p ou q é um valor que não está na árvore binária. Estou certo? Por exemplo LCA (8,20). ur código retorna 8. mas 20 não está presente na árvore binária
Javaman
3
Qual é o custo dessa solução? É eficiente? Parece continuar pesquisando mesmo depois de encontrar ambos peq. Isso ocorre devido à possibilidade de que peq não sejam únicos na árvore, pois não é um BST e pode conter duplicatas?
MikeB
3
@ MikeB, esta solução é definitivamente O (n), porque você percorre cada nó apenas uma vez no pior caso. Peter Lee, este é o mais eficiente que você pode fazer sem usar os indicadores dos pais. Você tem uma solução melhor?
gsingh2011
8
a primeira solução imperfeita deve ser eliminada de modo que não está confundindo
Zinan Xing
50

Aqui está o código de trabalho em 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
fonte
4
Isso não funciona quando um nó não existe na árvore.
Pratik Khadloya
você otimizaria seu código se a árvore fornecida fosse um BST?
Mona Jalal
1
"Se a raiz é uma de a ou b, então é a ACV." isso pode não ser verdade. O que você sabe neste momento é que não precisa verificar nenhum de seus filhos para encontrar a ACV. Isso acontece porque, posteriormente, podemos verificar se, para o pai da raiz, houve correspondências nos dois ramos (LCA é pai) ou apenas em um deles (nesse caso, um pode ser o LCA ou um ancestral ainda maior, o LCA )
andresp
28

As respostas dadas até agora usam recursão ou armazenam, por exemplo, um caminho na memória.

Ambas as abordagens podem falhar se você tiver uma árvore muito profunda.

Aqui está minha opinião sobre essa questão. Quando verificamos a profundidade (distância da raiz) de ambos os nós, se forem iguais, podemos mover com segurança para cima dos dois nós em direção ao ancestral comum. Se uma das profundidades for maior, devemos mover para cima a partir do nó mais profundo enquanto permanecermos no outro.

Aqui está o 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;    

A complexidade do tempo desse algoritmo é: O (n). A complexidade do espaço desse algoritmo é: O (1).

Em relação ao cálculo da profundidade, podemos primeiro lembrar a definição: Se v é raiz, profundidade (v) = 0; Caso contrário, profundidade (v) = profundidade (pai (v)) + 1. Podemos calcular a profundidade da seguinte forma:

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;
CEGRD
fonte
6
Árvores binárias normalmente não têm uma referência ao elemento pai. A adição de uma referência pai pode ser feita sem nenhum problema, mas eu consideraria esse O (n) espaço auxiliar.
21413 John Kurlak
Há uma suposição sutil nesta solução. Se um nó é um pai direto ou indireto do outro (ou seja, o nó mais profundo está em uma árvore enraizada no nó mais raso), essa solução retorna o pai do nó mais raso como resultado. Dependendo de como você define o menor ancestral comum, pode não ser o que você deseja. Algumas definições exigirão que o próprio nó mais raso seja o pai. Nesse caso, você precisaria rastrear qual é o nó mais raso e retorná-lo.
Srikanth
8

Bem, isso depende da estrutura da sua árvore binária. Presumivelmente, você tem alguma maneira de encontrar o nó da folha desejado, dada a raiz da árvore - basta aplicar isso a ambos os valores até que os galhos escolhidos divergam.

Se você não tem como encontrar a folha desejada, dada a raiz, sua única solução - tanto na operação normal quanto no último nó comum - é uma busca de força bruta na árvore.

Nick Johnson
fonte
8

Isso pode ser encontrado em: - 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
fonte
você pode me dizer como o seu código se comportará se p estiver presente, mas q não estiver presente na árvore? Da mesma forma, peq não estão presentes. Obrigado!!!
Tentando
Qual é o grande O em termos de tempo? Eu acho que é O (n * log (n)), dois lentos.
Peter Lee
6

Para descobrir o ancestral comum de dois nós: -

  • Localize o nó Nó1 na árvore usando a pesquisa binária e salve todos os nós visitados neste processo em uma matriz, digamos A1. Tempo - O (logn), Espaço - O (logn)
  • Encontre o Nó2 especificado na árvore usando a pesquisa binária e salve todos os nós visitados neste processo em uma matriz, por exemplo A2. Tempo - O (logn), Espaço - O (logn)
  • Se a lista A1 ou A2 estiver vazia, então um nó não existe e, portanto, não há ancestral comum.
  • Se a lista A1 e a lista A2 não estiverem vazias, procure na lista até encontrar o nó não correspondente. Assim que você encontrar esse nó, o nó anterior a esse é ancestral comum.

Isso funcionaria para a árvore de pesquisa binária.

Vipin
fonte
2
Ele afirmou claramente que a árvore NÃO é necessariamente uma BST.
Peter Lee
@ Peter Lee - A lógica acima funcionaria mesmo para qualquer árvore binária com uma simples alteração. Em vez da pesquisa binária de determinados nós, aplique a pesquisa linear (ou seja, qualquer passagem, mas deve ser a mesma para ambos os casos). O tempo de execução fora do curso seria O (n) em vez de O (logn). De fato, esse algo é o mais robusto quando o ponteiro pai não está disponível. (Viz. 'Codaddict') O algoritmo rucursive dada por muitos não funcionará quando um de determinado nó não pertence à árvore)
KGhatak
3

O algoritmo recursivo abaixo será executado em O (log N) para uma árvore binária balanceada. Se um dos nós passados ​​para a função getLCA () for o mesmo que a raiz, a raiz será o LCA e não haverá necessidade de executar nenhuma recussão.

Casos de teste. [1] Ambos os nós n1 e n2 estão na árvore e residem em ambos os lados do nó pai. [2] O nó n1 ou n2 é a raiz, o LCA é a raiz. [3] Somente n1 ou n2 está na árvore, o LCA será o nó raiz da subárvore esquerda da raiz da árvore ou o LCA será o nó raiz da subárvore direita da raiz da árvore.

[4] Nem n1 nem n2 estão na árvore, não há ACV. [5] Ambos n1 e n2 estão em uma linha reta um ao lado do outro, o LCA será um dos n1 ou n2 que está sempre próximo à raiz da árvore.

//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
fonte
3

Apenas desça da árvore inteira, rootdesde que os dois nós, digamos, pe qpara os quais o Ancestor seja encontrado, estejam na mesma subárvore (o que significa que seus valores são menores ou maiores que os da raiz).

Isso caminha diretamente da raiz para o menos ancestral comum, sem olhar para o resto da árvore, por isso é praticamente o mais rápido possível. Algumas maneiras de fazer isso.

Iterativo, espaço O (1)

Pitão

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

em caso de estouro, eu faria (root.val - (long) p.val) * (root.val - (long) q.val)

Recursivo

Pitão

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
fonte
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
fonte
2

Considere esta árvore insira a descrição da imagem aqui

Se fizermos a travessia pós-encomenda e pré-encomenda e encontrarmos o primeiro predecessor e sucessor comum, obteremos o ancestral comum.

pós-encomenda => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 pré-encomenda => 7,3,1,0,2,6,4 5,12,9,8,11,10,13,15,14

  • por exemplo: 1

Ancestral menos comum de 8,11

em pós-encomenda temos => 9,14,15,13,12,7 após 8 e 11 em pré-encomenda temos => 7,3,1,0,2,6,4,5,12,9 antes de 8 e 11

9 é o primeiro número comum que ocorre após 8 e 11 na pós-encomenda e antes de 8 e 11 na pré-encomenda, portanto 9 é a resposta

  • por exemplo: 2

Menos ancestral comum de 5,10

11,9,14,15,13,12,7 na pré-encomenda 7,3,1,0,2,6,4 na pré-encomenda

7 é o primeiro número que ocorre após 5,10 na pós-encomenda e antes de 5,10 na pré-encomenda, portanto 7 é a resposta

nnc
fonte
2

Se for uma árvore binária completa com filhos do nó x como 2 * x e 2 * x + 1, haverá uma maneira mais rápida de fazê-lo.

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. obter bits necessários para representar x & y que usando pesquisa binária é O (log (32))
  2. o prefixo comum da notação binária de x e y é o ancestral comum
  3. o que for representado por um maior número de bits é trazido para o mesmo bit por k >> diff
  4. k = x ^ y apaga o prefixo comum de x & y
  5. encontre bits representando o sufixo restante
  6. desloque x ou y por bits de sufixo para obter o prefixo comum, que é o ancestral comum.

Isso funciona porque basicamente divide o número maior por dois recursivamente até que ambos os números sejam iguais. Esse número é o ancestral comum. Dividir é efetivamente a operação de turno certo. Então, precisamos encontrar um prefixo comum de dois números para encontrar o ancestral mais próximo

hacker codificador
fonte
2

No scala, você pode:

  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
fonte
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;
    }
HeadAndTail
fonte
0

Aqui está a maneira C ++ de fazer isso. Tentaram manter o algoritmo o mais fácil possível para 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;
  }
};

Como usá-lo:

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

A maneira mais fácil de encontrar o antepassado comum mais baixo é usando o seguinte algoritmo:

Examine o nó raiz

se value1 e value2 forem estritamente menores que o valor no nó raiz 
    Examinar subárvore esquerda
caso contrário, se value1 e value2 forem estritamente maiores que o valor no nó raiz 
    Examine a subárvore direita
outro
    raiz 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;
} 
user2182531
fonte
6
Não é um BST!
Peter Lee
0

Eu encontrei uma solução

  1. Tomar em ordem
  2. Fazer pré-encomenda
  3. Fazer pós-encomenda

Dependendo de três percursos, você pode decidir quem é o LCA. No LCA, encontre a distância dos dois nós. Adicione essas duas distâncias, que é a resposta.

Rajdeep Sardar
fonte
0

Aqui está o que eu penso,

  1. Encontre a rota para o primeiro nó, armazene-a em arr1.
  2. Comece a encontrar a rota para o nó 2, enquanto faz isso, verifique todos os valores da raiz ao arr1.
  3. Quando o valor for diferente, saia. O antigo valor correspondente é o LCA.

Complexidade: passo 1: O (n), passo 2 = ~ O (n), total = ~ O (n).

badri.coder
fonte
0

Aqui estão duas abordagens em c # (.net) (ambas discutidas acima) para referência:

  1. Versão recursiva de localização de LCA na árvore binária (O (N) - como no máximo cada nó é visitado) (os principais pontos da solução é LCA é (a) único nó na árvore binária em que ambos os elementos residem nos dois lados das subárvores (esquerda e à direita) é LCA. (b) E também não importa qual nó está presente em ambos os lados - inicialmente eu tentei manter essas informações e, obviamente, a função recursiva se tornou tão confusa.Depois que percebi, ficou muito elegante.

  2. Pesquisando ambos os nós (O (N)) e mantendo o controle de caminhos (usa espaço extra -, o número 1 é provavelmente superior, mesmo que o espaço seja provavelmente insignificante se a árvore binária estiver bem equilibrada, pois o consumo de memória extra será apenas O (log (N)).

    para que os caminhos sejam comparados (essencialmente semelhantes à resposta aceita - mas os caminhos são calculados assumindo que o nó do ponteiro não está presente no nó da árvore binária)

  3. Apenas para a conclusão ( não relacionada à pergunta ), LCA no BST (O (log (N))

  4. Testes

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

onde a versão recursiva privada acima é invocada pelo seguinte 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;
        }

Solução, acompanhando os caminhos dos dois nós:

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

onde FindNodeAndPath é definido 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) - não relacionado (apenas para conclusão para referência)

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

Testes unitários

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

Se alguém interessado em pseudo-código (para trabalhos domésticos em universidades), aqui está um.

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.
fonte
0

Embora isso já tenha sido respondido, esta é minha abordagem para esse problema usando a linguagem de programação C. Embora o código mostre uma árvore de pesquisa binária (no que diz respeito a insert ()), o algoritmo também funciona para uma árvore binária. A idéia é passar por todos os nós que se encontram do nó A ao nó B no percurso em ordem, procurando os índices para eles no percurso pós-ordem. O nó com índice máximo na travessia pós-ordem é o menor ancestral comum.

Este é um código C em funcionamento para implementar uma função para encontrar o menor ancestral comum em uma árvore binária. Também estou fornecendo todas as funções utilitárias, etc., mas pule para CommonAncestor () para entender rapidamente.

#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
fonte
0

Pode haver mais uma abordagem. No entanto, não é tão eficiente quanto o já sugerido nas respostas.

  • Crie um vetor de caminho para o nó n1.

  • Crie um segundo vetor de caminho para o nó n2.

  • Vetor de caminho que implica os nós definidos a partir daquele que seria percorrido para alcançar o nó em questão.

  • Compare os dois vetores de caminho. O índice em que são incompatíveis retorna o nó nesse índice - 1. Isso daria o LCA.

Contras para esta abordagem:

Precisa percorrer a árvore duas vezes para calcular os vetores do caminho. Precisa de espaço O (h) adicional para armazenar vetores de caminho.

No entanto, isso é fácil de implementar e entender também.

Código para calcular o vetor de caminho:

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
fonte
0

Tente assim

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
fonte
0

Maneira bruta:

  • Em cada nó
    • X = encontre se um dos n1, n2 existe no lado esquerdo do nó
    • Y = encontre se um dos n1, n2 existe no lado direito do nó
      • se o próprio nó for n1 || n2, podemos chamá-lo ou encontrado à esquerda ou à direita para fins de generalização.
    • Se X e Y forem verdadeiros, o Nó é a CA

O problema com o método acima é que faremos o "find" várias vezes, ou seja, existe a possibilidade de cada nó ser percorrido várias vezes. Podemos superar esse problema se conseguirmos registrar as informações para não processá-las novamente (pense em programação dinâmica).

Portanto, em vez de encontrar todos os nós, mantemos um registro do que já foi encontrado.

Melhor maneira:

  • Verificamos se, para um determinado nó, se left_set (ou seja, n1 | n2 foi encontrado na subárvore esquerda) ou right_set de maneira profunda, primeiro. (NOTA: Estamos dando à própria raiz a propriedade de ser left_set se for n1 | n2)
  • Se left_set e right_set, o nó é um 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
fonte
0

Código para uma primeira amplitude de pesquisa para garantir que ambos os nós estejam na árvore. Somente então avance com a pesquisa LCA. Por favor, comente se você tem alguma sugestão para melhorar. Acho que provavelmente podemos marcá-los como visitados e reiniciar a pesquisa em um determinado ponto em que paramos para melhorar o segundo nó (se ele não for encontrado VISITE)

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
fonte
0

Você está certo de que, sem um nó pai, a solução com travessia fornecerá complexidade de tempo O (n).

Abordagem transversal Suponha que você esteja encontrando LCA para os nós A e B, a abordagem mais direta é primeiro obter o caminho da raiz para A e, em seguida, obter o caminho da raiz para B. Depois de ter esses dois caminhos, é possível iterá-los facilmente e encontre o último nó comum, que é o menor ancestral comum de A e B.

Solução recursiva Outra abordagem é usar a recursão. Primeiro, podemos obter LCA da árvore esquerda e da árvore direita (se existir). Se A ou B for o nó raiz, a raiz será o LCA e retornaremos a raiz, que é o ponto final da recursão. À medida que continuamos dividindo a árvore em subárvores, eventualmente, atingimos A e B.

Para combinar soluções de subproblemas, se LCA (árvore esquerda) retornar um nó, sabemos que A e B localizam na árvore esquerda e o nó retornado é o resultado final. Se LCA (esquerda) e LCA (direita) retornarem nós não vazios, significa que A e B estão na árvore esquerda e direita, respectivamente. Nesse caso, o nó raiz é o nó comum mais baixo.

Verifique o menor ancestral comum para análise e solução detalhadas.

Marca
fonte
0

Algumas das soluções aqui assumem que há referência ao nó raiz, outras assumem que a árvore é uma BST. Compartilhar minha solução usando o hashmap, sem referência ao rootnó e à árvore, pode ser BST ou não-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
fonte
0

Solução 1: Recursiva - Mais Rápida

  • A idéia é atravessar a árvore a partir da raiz. Se qualquer uma das teclas dadas p e q corresponder à raiz, a raiz será LCA, assumindo que ambas estejam presentes. Se o root não corresponder a nenhuma das chaves, recursamos pela subárvore esquerda e direita.
  • O nó que tem uma chave presente na subárvore esquerda e a outra chave presente na subárvore direita é o LCA. Se ambas as chaves estiverem na subárvore esquerda, a subárvore esquerda também terá LCA, caso contrário, o LCA ficará na subárvore direita.
  • Complexidade temporal: O (n)
  • Complexidade do espaço: O (h) - para pilha de chamadas 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)
    }
}

Solução 2: Iterativo - Usando ponteiros pai - Mais lento

  • Crie uma tabela de hash vazia.
  • Insira p e todos os seus ancestrais na tabela de hash.
  • Verifique se q ou algum de seus ancestrais existe na tabela de hash; se sim, retorne o primeiro ancestral existente.
  • Complexidade do tempo: O (n) - No pior caso, podemos estar visitando todos os nós da árvore binária.
  • Complexidade do espaço: O (n) - O espaço utilizado pelo ponteiro pai Hash-table, ancestor_set e fila, seria O (n) cada.
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
fonte