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
    12 окт 2020 в 12:43
  • @strawdog задача была задана именно в таком виде и именно так требуется называть функцию в ответе, иначе не пройдет тесты
    – braflovsky
    12 окт 2020 в 12:50
  • а отступы в два пробела тоже требование такое?
    – strawdog
    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
    13 окт 2020 в 7:08

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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