BST全深并发症

Question

以下是一个正在工作的BST的摘录：

class BinaryTree():

    def __init__(self,rootid):
      self.left = None
      self.right = None
      self.rootid = rootid
    def getLeftChild(self):
        return self.left
    def getRightChild(self):
        return self.right
    def setNodeValue(self,value):
        self.rootid = value
    def getNodeValue(self):
        return self.rootid

我决定不展示上面课程的每一个功能，只展示我要实现的重要功能。在

我希望计算树中每个节点的总深度，并尝试使用以下函数：

^{pr2}$

count=1表示根节点的深度为1。在

但是，这个函数的问题是，当它到达一个None节点时，它会崩溃，我不知道如何修复它。在

这是我尝试使用函数时收到的错误消息：

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

有人能帮我吗？在

Answer 1

递归函数depth需要一个中断条件：

def depth(tree):
    if tree == None:
        return 0
    else:
        return 1 + max(depth(tree.getLeftChild()), depth(tree.getRightChild()))

你在子树的深处忘了一个max。在

上面的代码段在tree == None时就失败了（当节点在任何一侧都没有子节点时）。然后不返回任何内容，这在Python中隐式返回None。在