A Wikipedia contém uma página sobre Tree Traversal que inclui pseudo-códigos para iterar sobre árvore binárias usando pilhas. Por exemplo, este é do Pre-order Traversal:
iterativePreorder(node)
parentStack = empty stack
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
visit(node) #1
parentStack.push(node) #2
node = node.left
else
node = parentStack.pop() #3
node = node.right
Anotei três pontos (#1, #2, #3), os quais irei comentar adiante.
Entretanto, para a resolução do problema em questão (LCA), não limitando-se a dois descendentes por nó (árvore binária), são necessários alguns ajustes:
- Uma pilha auxiliar para armazenar o filho atual sendo visitado a cada nível que o algoritmo desce na árvore. Diferente de uma árvore binária, onde basta percorrer o nó da esquerda e depois o da direita, para percorrer um nó com
n
filhos precisamos de um contador. E como cada filho pode ter m
filhos, então deve haver um contador para cada nível da árvore.
- Uma segunda pilha auxiliar para armazenar o caminho até o primeiro nó encontrado. Como um dos objetivos do algoritmo é encontrar dois nós, devemos armazenar o caminho até o primeiro e continuar até encontrar o segundo.
Um pseudo-código para encontrar o ancestral mais próximo dos nós p
e q
, dada a raiz node
, ficou assim:
findClosestCommonAncestor(node, p, q)
parentStack = empty stack
childIndexStack = empty stack
firstNodePath = null
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
#1
if (node == p || node == q)
if (firstNodePath ≠ null)
parentStack.add(node)
int n = min(parentStack.length, firstNodePath.length)
for i = (n - 1)..0
if (parentStack(i) == firstNodePath(i))
return parentStack(i)
return null
else
firstNodePath = copy parentStack
firstNodePath.push(node)
#2
if (not empty node.children)
parentStack.push(node)
childIndexStack.push(0)
node = node.children(0)
else
node = null
else
#3
node = parentStack.peek()
i = childIndexStack.pop() + 1
if (i >= node.children.length)
node = null
parentStack.pop()
else
node = node.children(i)
childIndexStack.push(i)
Certamente ficou mais complexo, mas o conceito é basicamente o mesmo do anterior. Note que também marquei neste algoritmo três pontos, pois são análogos ao anterior. Vejamos:
- #1 Este é o bloco onde o valor do nó atual é processado. O
visit(node)
do primeiro algoritmo foi substituído por um bloco que verifica se um dos nós foi encontrado. Caso tenha encontrado o primeiro nó ele salva a pilha atual. Caso tenha encontrado os dois ele compara as pilhas, item a item, procurando pelo pai mais próximo.
- #2 O algoritmo inicial adiciona o nó atual na pilha e avança para o filho da esquerda. O segundo algoritmo generaliza para
n
filhos avançando para o primeiro filho (0).
- #3 O algoritmo inicial desempilha um nó e avança para o filho da direita. O segundo algoritmo generaliza avançando para o próximo filho (anterior + 1).
O código em Java ficou assim:
class Node {
List<Node> children = new ArrayList<Node>();
Integer id;
Node(Integer id) {
this.id = id;
}
}
Node findClosestCommonAncestor(Node node, Node p, Node q) {
Stack<Node> parentStack = new Stack<Node>();
Stack<Integer> childIndexStack = new Stack<Integer>();
Stack<Node> firstNodePath = null;
while (!parentStack.empty() || node != null) {
if (node != null) {
if (node == p || node == q) {
if (firstNodePath != null) {
parentStack.add(node);
int n = Math.min(parentStack.size(), firstNodePath.size());
for (int i = n - 1; i >= 0; i--) {
if (parentStack.get(i) == firstNodePath.get(i)) {
return parentStack.get(i);
}
}
return null;
} else {
firstNodePath = new Stack<Node>();
firstNodePath.setSize(parentStack.size());
Collections.copy(firstNodePath, parentStack);
firstNodePath.push(node);
}
}
if (!node.children.isEmpty()) {
parentStack.push(node);
childIndexStack.push(0);
node = node.children.get(0);
} else {
node = null;
}
} else {
node = parentStack.peek();
Integer i = childIndexStack.pop() + 1;
if (i >= node.children.size()) {
node = null;
parentStack.pop();
} else {
node = node.children.get(i);
childIndexStack.push(i);
}
}
}
return null;
}
A versão completa do código Java está disponível para edição e teste no ideone.com.
Atualização
Ao contrário do enunciado proposto na pergunta, se houvesse a informação do nó pai e não dos filhos, um algoritmo bem mais eficiente poderia ser proposta.
Suponha que são dados dois nós P
e Q
. Esse algoritmo precisa apenas:
- Armazenar
P
e seus pais os nós num conjunto C
- Percorrer os pais de
Q
, começando do próprio elemento e retornar o primeiro elemento Q(i)
que esteja no conjunto C
.
Código em Java:
static class Node {
Node parent;
Integer id;
Node(Integer id, Node parent) {
this.id = id;
this.parent = parent;
}
public String toString() {
return id.toString();
}
}
static Node findClosestCommonAncestor(Node p, Node q) {
if (p == null || q == null) return null;
//guarda os pais do nó P, incluindo o próprio
Set<Node> parentsOfP = new HashSet<Node>();
while (p != null) {
parentsOfP.add(p);
p = p.parent;
}
//procura o primeiro pai de Q que está entre os pais de P
while (q != null) {
if (parentsOfP.contains(q)) {
return q;
}
q = q.parent;
}
return null;// not in the same tree
}