BST的高度比预期高+1

Question

我做了一个函数来确定BST的高度，但是当树的高度为2时，我看到的结果是3，等等。我不知道我应该在代码中更改什么。如果您需要完整的代码才能回答我，请告诉我，我会复制它

def maxDepth(self, node):
    if node is None:
        return 0

    else:

        # Compute the depth of each subtree
        lDepth = self.maxDepth(node.left)
        rDepth = self.maxDepth(node.right)

        # Use the larger one
        if (lDepth > rDepth):
            return lDepth + 1
        else:
            return rDepth + 1

Answer 1

只需执行return -1即可将所需高度减小1，而不是return 0。更正代码如下：

def maxDepth(self, node):
    if node is None:
        return -1
    else:
        # Compute the depth of each subtree
        lDepth = self.maxDepth(node.left)
        rDepth = self.maxDepth(node.right)

        # Use the larger one
        if (lDepth > rDepth):
            return lDepth + 1
        else:
            return rDepth + 1

您还可以使用内置的max()函数缩短代码：

def maxDepth(self, node):
    if node is None:
        return -1
    return max(self.maxDepth(node.left), self.maxDepth(node.right)) + 1

---

注意：OP是正确的，高度应基于边，即具有一个节点的树5的高度应为0。空树（无树）的高度为-1。这有两个证明：

维基百科中的一个证据说高度是基于边缘的，并且

在著名的书Cormen T.H. - Introduction to Algorithms中还有另一个证据：