Solução por Lucca Siaudzionis
Este problema é um problema básico se for resolvido pelo algoritmo do Mínimo Ancestral Comum (LCA – Lowest Common Ancestor). Há duas maneiras típicas de fazer, uma em $$O(n \ lg n)$$ e outra em $$O(n \ \sqrt{n} )$$. Você pode aprender a fazer o o LCA em $$O(n \ \log{n})$$ na nossa aula do Curso Noic de Informática, clicando aqui. Além disso, um material que explica (em português!) muito bem o LCA em $$O(n \ \sqrt{n})$$ pode ser visto neste link.
Seguindo o mesmo estilo que se faz no material, o código fica assim:
https://gist.github.com/luccasiau/a3c5cdc717557b463ef0
Deixe um comentário