Python 中的二叉树大小函数

Question

我写了几个函数来计算二叉树的大小。第一个（函数 1）工作得很好并且在 class 之外声明，它不是 class 的成员函数。然而，第二个是 class 的成员函数却给我带来了奇怪的结果。我很迷惑！任何帮助将不胜感激。

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:

如果其中之一是None，return 0

如果左边是None

，你至少需要得到右边的大小+1

我想你需要这样的东西：

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 计算为 return 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

Python 中的二叉树大小函数

Binary Tree Size function in Python

python

binary-tree