1

Дано два бинарных дерева. Надо посчитать, сколько раз первое дерево встречается во втором.

Например

   tree1 = Node ( Node ( None , None ), Node ( None , None )) 
   tree2 = Node ( None , Node ( Node ( None , None ), Node ( None , None ))) 
         
   print ( count ( tree1 , tree2 )) # ответ 1 

Решение пока есть только такое, но оно находит только одно повторение, если есть.

from collections import namedtuple
def count ( node1, node2 ):
  if not node1 and not node2:
    return 0
  elif not node1 or not node2:
    return 0
  elif (node2.left or node2.right) and (node1 == node2 or node1 in node2):
    return 1
  return count(node1, node2.left) + count(node1,node2.right)

Как посчитать все повторения? Вот к примеру в таком случае ответ должен быть 2.

tree1 = Node(left=Node(left=None, right=Node(left=None, right=None)), right=None)

tree2 = Node(left=Node(left=Node(left=None, right=Node(left=None, right=None)), right=None), right=Node(left=Node(left=None, right=Node(left=None, right=None)), right=None))

print(count(tree1,tree2)) # 2
3
  • Отформатируйте код в вопросе нормально. Не следует называть свои функции так же, как встроенные методы/функции языка pyhton.
    – strawdog
    Commented 12 окт. 2020 в 12:43
  • @strawdog задача была задана именно в таком виде и именно так требуется называть функцию в ответе, иначе не пройдет тесты
    – braflovsky
    Commented 12 окт. 2020 в 12:50
  • а отступы в два пробела тоже требование такое?
    – strawdog
    Commented 12 окт. 2020 в 13:40

1 ответ 1

1

Кучерявенькая рекурсия получилась :)

class Node:
    def __init__(self, left, right):
        self.right = right
        self.left = left
    def __str__(self):
        return f'Node({self.left}, {self.right})'


def count_same(sub, tree):
    def is_same(sub, tree):
        if sub is None:
            return tree is None

        return (tree is not None 
            and is_same(sub.left, tree.left) 
            and is_same(sub.right, tree.right))

    if sub is None:
        return (1 if tree is None 
            else count_same(sub, tree.right) + count_same(sub, tree.left))


    if tree is None:
        return 0

    return (count_same(sub, tree.right) 
        + count_same(sub, tree.left) 
        + int(is_same(sub.left, tree.left) and is_same(sub.right, tree.right))
    )



tree1 = Node ( Node ( None , None ), Node ( None , None )) 
tree2 = Node ( None , Node ( Node ( None , None ), Node ( None , None ))) 

res = count_same(tree1, tree2)
assert res == 1, f'assert {res} == 1'
 
tree1 = Node ( None , None )
tree2 = Node ( None , Node ( Node ( None , None ), Node ( None , None ))) 

res = count_same(tree1, tree2)
assert res == 2, f'assert {res} == 2'
   
tree1 = None
tree2 = Node ( None , Node ( Node ( None , None ), Node ( None , None ))) 

res = count_same(tree1, tree2)
assert res == 5, f'assert {res} == 5'
   
tree1 = Node ( Node ( None , None ), Node ( None , None )) 
tree2 = Node ( Node ( None , None ), Node ( Node ( None , None ) , None )) 

res = count_same(tree1, tree2)
assert res == 0, f'assert {res} == 0'
1
  • 1
    Очень кучерявенькая) Спасибо, работает)
    – braflovsky
    Commented 13 окт. 2020 в 7:08

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.