binary-tree - 被引用最多的二叉树深度计算算法有什么问题？

Question

有东西吃进我的脑子里：下面这棵树的深度怎么可能

  b
 / \
a   c

be 3，在被引用最多的算法之后（这里是Java）：

int depth(Node n)
{
    if(n == null)
    {
        return 0;
    }

    int lDepth = depth(n.left);
    int rDepth = depth(n.right);

    return 1 + ((lDepth > rDepth) ? lDepth : rDepth);
}

当只有一个（根）节点的树的深度0根据维基百科和我的许多其他来源定义为最深节点的路径长度时？显然，只有一个节点的树到最深节点的路径长度为0，而上述算法永远不会产生小于 的任何值1。

是具有单个根节点的树的深度0还是它1？如果是，0那么上面的算法就是错误的，因为它会产生1.

我从没想过这样一件微不足道的事情会在我身上发生翻天覆地的变化。

Answer 1

一棵树的高度通常定义为：

1. The number of edges on the longest path from the root to a leaf

或者

2. The number of nodes on the longest path from the root to a leaf

当然，您可以轻松地将上述任何定义给出的结果转换为另一个结果 - 只需减去/加 1。

你是对的，第一个定义被更频繁地使用。

如您所见，您所依据的算法遵循第二个定义。