一种递归方法,用于查找任何(不一定是完整的)二叉树的深度

Question

我试图以递归方式计算O(log n)时间内任何(不一定是完整的)BST的深度.

这是我提出的算法:

//max() - returns the max of two numbers
int depth(root)
{
    if(root->left==NULL && root->right==NULL) //leaf
        return 0;
    else if(root->left!=NULL && root->right==NULL) //with right leaf
        return( max(depth(root->left),0)+1);
    else if(root->left==NULL && root->right!=NULL) //with left leaf
        return( max(0,depth(root->right)+1);
    else if(root->left->left==NULL && root->left->right==NULL && root->right->left==NULL&&root->right->right==NULL) // this a parent of two leaves
        return 1; 
    else// for the condition that this a parent of two sub roots
        return( max(depth(root->right),depth(root->left))+1);
}

这个算法在O(log n)时间内计算深度是否合适？

有没有更好的办法？

Answer 1

这是O(n)时间,因为你可以遍历每个节点.您可以在O(log n)中搜索二进制搜索树,但除非在构建深度或执行类似操作时缓存深度,否则无法在O(n)中找到二叉树的深度.

您可能需要注意两种特殊情况.

一个完美的二叉树可以有其深度为O确定(log n)的.这意味着每片叶子处于同一水平.

如果已知节点数,则完整且平衡的二叉树可以使其深度近似为O(log n)或O(1).这将是近似值(通常为+/- 1).