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

Question

我想计算二进制搜索树的每个节点的深度的总和.

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

Answer 1

像这样的东西:

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

现在有一个希望提供信息的解释,以防这是家庭作业.计算节点数非常简单.首先,如果节点不是node(node == null),它返回0.如果它是一个节点,它首先计算它的self(the 1),加上它左边子树中的节点数加上节点中的节点数.它的右子树.另一种思考方式是通过BFS访问每个节点,并为您访问的每个节点添加一个计数.

深度的总和是类似的,除了不为每个节点仅添加一个,该节点添加其自身的深度.它知道自己的深度,因为它的父母告诉它.每个节点都知道它的子节点的深度是它自己的深度加一,所以当你得到一个节点的左右子节点的深度时,你告诉它们它们的深度是当前节点的深度加1.

而且,如果节点不是节点,则它没有深度.因此,如果您想要所有根节点的子节点的深度总和,则传入根节点和根节点的深度,如下所示:sumDepthOfAllChildren(root, 0)

递归是非常有用的,它只是一种非常不同的思考方式,并使实践习惯于它

Answer 2

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

Answer 3

这个解决方案更加简单。

public int getHeight(Node root)
{
    if(root!=null)
        return 1+ Math.max(getHeight(root.leftchild),getHeight(root.rightchild));
    else
        return 0;
}

Answer 4

对于任何给定的树，根节点的数量为 1 加上左子树中的节点数加上右子树中的节点数:)

细节（例如确保确实存在左子树或右子树）“留给读者”。