Найти максимальную разницу между количеством правых и левых узлов бинарного дерева

Question

Мне нужно найти максимальную разницу между количеством правых и левых узлов бинарного дерева Например у дерева 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))

Answer 1

Вроде так должно работать:

def diff(node):
    if not node:
        return 0

    difference = abs(countSide(node.left) - countSide(node.right))
    
    return max(difference, diff(node.right), diff(node.left))

БЛОГ НА HUSL

Найти максимальную разницу между количеством правых и левых узлов бинарного дерева

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