Функция двоичного дерева в Python

Question

Я написал несколько функций для вычисления размера двоичного дерева. Первый (функция 1) работает отлично и объявлен вне класса, он не является функцией-членом класса. Однако второй, который является функцией-членом класса, дает мне странные результаты. Я запутался! Любая помощь будет оценена по достоинству.

Function 1 
    def size(root): 
     if root is None: 
      return 0 
     else: 
      return size(root.left)+ 1+ size(root.right) 


Function 2 
    def size(self): 
     if self.left is None or self.right is None: 
       return 0 
     else: 
       return self.left.size()+1+self.right.size() 

Answer 1

if self.left is None or self.right is None: 

, если один из них не является Нет, вернуться 0

вам нужно, по крайней мере, получить размер справа + 1, если оставить не None

Я думаю, что нужно что-то вроде :

leftSize = self.left.size() if self.left else 0 
rightSize = self.right.size() if self.right else 0 
return leftSize + 1 + rightSize 

Я не пробовал.

Answer 2

Вторая функция не является точным, например

x = Tree() 
x.left = Tree() 
x.right = None 

В приведенном выше примере, x.size() будет оценивать до нуля, так как вы рассматриваете либо left is None или right is None возвращает 0 (что тривиально для выше пример). Вам нужно настроить свою логику.

def size(self): 
    total = 1 #any instantiated object has a size of at least 1. 
    if self.left is not None: #feel free to add additional validity checks, i.e. instanceof(Tree...) 
     total += self.left.size() 
    if self.right is not None: 
     total += self.right.size() 
    return total