Dada uma árvore binária e dois nós dela, desenvolva um algoritmo para achar o ancestral comum mais baixo dos dois nós dados. O ancestral comum é um nó que possua os outros dois nós em suas subárvores. O ancestral comum mais baixo é o ancestral comum que tem a maior profundidade.

Passo 1

A questão pede para encontrarmos, em uma árvore binária, o ancestral comum mais baixo (LCA) de dois nós p e q. O conteúdo é recursão em árvores e vamos usar a ideia de percorrer subárvores e detectar onde p e q aparecem.

Passo 2

A estratégia é usar uma função recursiva LCA(u,p,q) que, ao receber o nó atual u, retorne: u mesmo se u for nulo ou igual a p ou igual a q. Isso trata os casos em que encontramos um dos alvos ou chegamos ao fim de um ramo. Se u não for nem nulo nem um dos alvos, chamamos recursivamente:
• left = LCA(u.left, p, q)
• right = LCA(u.right, p, q)

Passo 3

Agora analisamos os resultados dessas chamadas:
• Se left ≠ null e right ≠ null, significa que p e q estão em subárvores diferentes de u, logo u é o LCA.
• Se apenas left ≠ null, o LCA está na subárvore esquerda; retornamos left.
• Se apenas right ≠ null, o LCA está na subárvore direita; retornamos right.
Isso garante que, subindo na recursão, o primeiro nó que encontra p e q em lados distintos será o ancestral comum mais baixo.

Resposta

Segue o pseudocódigo da função LCA:
function LCA(u, p, q):
if u == null or u == p or u == q:
return u
left = LCA(u.left, p, q)
right = LCA(u.right, p, q)
if left != null and right != null:
return u
if left != null:
return left
else:
return right

Exercícios relacionados