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

Question

我想计算二叉搜索树每个节点深度的总和。

元素的各个深度尚未存储。

Answer 1

像这样:

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

并得到每个 child 的深度总和:

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);
}

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

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

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

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