Сколько раз одно бинарное дерево встречается во втором?

Question

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

Например

   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

Answer 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'

БЛОГ НА HUSL

Сколько раз одно бинарное дерево встречается во втором?

Ответы (1 шт):