Мне нужно найти максимальную разницу между количеством правых и левых узлов бинарного дерева
Например у дерева tree = Node(None,Node(Node(None,None),Node(None,None)))
максимальная разница будет у корня: слева 0 узлов, справа 3, значит разница 3
А у дерева tree = Node(Node(Node(None,None),Node(Node(None,None),None)),Node(Node(None,None),Node(Node(Node(Node(None,None),Node(Node(None,None),Node(None,None))),None),None)))
максимальная разница будет в узле на первом уровне справа (7-1=6)
Мне удалось посчитать разницу правых и левых узлов корня, но я не понимаю, как бы это все рекурсивно прогнать по всем узлам и найти максимальную разницу во всем дереве.
from collections import namedtuple
def countSide(node):
if not node:
return 0
return countSide(node.left)+countSide(node.right)+1
def diff(node):
if not node:
return 0
max = 0
difference = abs(countSide(node.left) - countSide(node.right))
if difference > max:
max = difference
return max
tree = Node(Node(Node(None,None),Node(Node(None,None),None)),Node(Node(None,None),Node(Node(Node(Node(None,None),Node(Node(None,None),Node(None,None))),None),None))) #6
print(diff(tree))