Найти «дядю» в бинарном дереве - Python

Question

моя миссия - построить функцию, которая возвращает число «дядей» в данном двоичном дереве. Узел - дядя, только если его брат (второй ребенок его отца) имеет детей. Это мой код: "

def uncle(root,count = None): 
    if count is None: 
     count = [0] 
    a,b = 0,0 
    if root.left: 
     if root.left.left or root.left.right: 
      a = uncle(root.left) 
      a = 1 
    if root.right: 
     if root.right.right or root.right.left: 
      b = uncle(root.right) 
      b = 1 
    if b > 0: 
     count[0] += 1 
    if a > 0: 
     count[0] += 1 
    return count[0] 

" И это класс bin_tree: "

Class bin_tree(): 
    def __init__(self,data, left_child = None, right_child = None): 
     self.data = data 
     self.left = left_child 
     self.right = right_child 

" Моя проблема заключается в следующем: Когда я переключился строки: а = дядя (root.left) a = 1 Это не сработало (значение = переменная a изменила свое значение на 0 по какой-то причине), и я абсолютно не знаю, почему .. Я думал, что это должно было сработать, потому что не имеет значения, если я сначала вызову функцию рекурсии или сначала скажу a = 1. Может кто-нибудь мне помочь?

Answer 1

Я не тестировал это, но он должен работать. Код, который вы написали, может быть значительно сокращен.

Для начала вы считаете список, когда это действительно не обязательно.

Ваши a и b никогда не будут использоваться, поэтому нет смысла назначать им что-либо. Вероятно, поэтому вы получаете ошибку, независимо от того, какое значение вы даете a или b.

Тогда вам не нужно проверять, больше ли a или b, чем 1. Вы можете просто увеличить счет, когда узнаете, что в дереве есть дядя.

Однако главная причина, по которой он не работает, заключается в том, что каждый раз, когда вы называете дядю, вы не передаете свой новый счет. Это означает, что оно принимает значение по умолчанию, которое вы указали как None. После этого список будет сброшен на [0]. Ну, действительно, новый список создан, который отличается от предыдущего, хотя и имеет одно и то же имя. Поэтому, хотя вы можете подумать, что вы обновляете один и тот же счет, это не так. Это проблема масштаба.

def uncle(root,count=0): 
    if root.left: 
     if root.left.left or root.left.right: 
      count = uncle(root.left, count) 
      count += 1 
    if root.right: 
     if root.right.right or root.right.left: 
      count = uncle(root.right, count) 
      count += 1 
return count