1

Мне нужно найти максимальную разницу между количеством правых и левых узлов бинарного дерева Например у дерева tree = Node(None,Node(Node(None,None),Node(None,None))) максимальная разница будет у корня: слева 0 узлов, справа 3, значит разница 3

пример 1

А у дерева 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) пример 2

Мне удалось посчитать разницу правых и левых узлов корня, но я не понимаю, как бы это все рекурсивно прогнать по всем узлам и найти максимальную разницу во всем дереве.

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))
2
  • а в первом случае справа от корня разве не 3 узла?
    – timur
    9 окт 2020 в 16:26
  • @timur да, конечно 3
    – braflovsky
    9 окт 2020 в 16:28

1 ответ 1

2

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

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))
1
  • И действительно. Благодарю!
    – braflovsky
    9 окт 2020 в 16:37

Ваш ответ

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

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