如何计算二叉搜索树的深度

像这样：

int countChildren(Node node)
{
    if ( node == null )
        return 0;
    return 1 + countChildren(node.getLeft()) + countChildren(node.getRight());
}

并得到每个孩子的深度总和：

int sumDepthOfAllChildren(Node node, int depth)
{
    if ( node == null )
        return 0;  // starting to see a pattern?
    return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) + 
                   sumDepthOfAllChildren(node.getRight(), depth + 1);
}

现在，希望能提供一个信息丰富的解释，以防万一这是家庭作业。计算节点数非常简单。首先，如果节点不是节点（），则返回0。如果它是一个节点，它首先计算其自身 （the ），加上其左子树中的节点数加上其右子树中的节点数。另一种思考方式是，您通过BFS访问每个节点，并在您访问的每个节点的计数中添加一个。node == null1

深度求和是相似的，只是节点不是为每个节点只添加一个，而是添加其自身的深度。它知道自我的深度，因为它的父母告诉了它。每个节点都知道它的子节点的深度是它自己的深度加一，所以当你得到一个节点的左子节点和右子节点的深度时，你告诉他们它们的深度是当前节点的深度加1。

同样，如果节点不是节点，则它没有深度。因此，如果您想要所有根节点子节点的深度之和，则可以传入根节点和根节点的深度，如下所示：sumDepthOfAllChildren(root, 0)

递归非常有用，它只是一种非常不同的思维方式，需要练习才能习惯它。

int maxDepth(Node node) {
    if (node == null) {
        return (-1); // an empty tree  has height −1
    } else {
        // compute the depth of each subtree
        int leftDepth = maxDepth(node.left);
        int rightDepth = maxDepth(node.right);
        // use the larger one
        if (leftDepth > rightDepth )
            return (leftDepth + 1);
        else
            return (rightDepth + 1);
    }
}