Duas ABBs são SIMILARES se possuem a mesma distribuição de nós (independente dos valores nos mesmos). Em uma definição mais formal, duas ABBs são SIMILARES se são ambas vazia, ou se suas subárvores esquerdas são similares, e suas subárvores direitas também são similares. Implemente a função que verifica se duas árvores são similares.
Passo 1
A ideia é comparar a forma (estrutura) das duas árvores abstratando os valores em cada nó.
Primeiro caso base: se as duas raízes forem None (árvores vazias), então são similares.
Segundo caso base: se uma raiz for None e a outra não, então não são similares.
Caso geral: se as duas raízes existem, a gente chama recursivamente a função nas subárvores esquerda e direita. Se em ambos os lados (esquerdo e direito) as chamadas recursivas retornarem True, então as árvores são similares.
Primeiro caso base: se as duas raízes forem None (árvores vazias), então são similares.
Segundo caso base: se uma raiz for None e a outra não, então não são similares.
Caso geral: se as duas raízes existem, a gente chama recursivamente a função nas subárvores esquerda e direita. Se em ambos os lados (esquerdo e direito) as chamadas recursivas retornarem True, então as árvores são similares.
Resposta
Definição de um nó numa ABB
class Node:
def init(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def init(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
Função que verifica se duas árvores são similares
def are_similar(root1, root2):
# Caso 1: ambas vazias → similares
if root1 is None and root2 is None:
return True
# Caso 2: uma está vazia e a outra não → não são similares
if root1 is None or root2 is None:
return False
# Caso recursivo: as duas existem → comparar esquerda e direita
return (are_similar(root1.left, root2.left) and
are_similar(root1.right, root2.right))
# Caso 1: ambas vazias → similares
if root1 is None and root2 is None:
return True
# Caso 2: uma está vazia e a outra não → não são similares
if root1 is None or root2 is None:
return False
# Caso recursivo: as duas existem → comparar esquerda e direita
return (are_similar(root1.left, root2.left) and
are_similar(root1.right, root2.right))