Time complexity# JobHunting - 待字闺中
d*o
1 楼
下面找lowestCommonAncestor的代码如果tree balance的话time complexity是多少?
自己想的不保险,请教一下。
我觉得是O(nlogn)
bool contain(node* root, node* cur)
{
if(root)
{
if(root==cur) return true;
return contain(root->left,cur)||contain(root->right,cur);
}
return false;
}
node* lowest(node* root, node* n1, node* n2)
{
if(root==n1||root==n2) return root;
if(root==NULL) return NULL;
bool isLeft1 = false;
bool isLeft2 = false;
if(root->left)
{
isLeft1 = contain(root->left,n1); //O(n)
isLeft2 = contain(root->left,n2);
}
if( isLeft1&&!isLeft2) return root;
if( !isLeft1&&isLeft2) return root;
if( isLeft1&&isLeft2) return lowest(root->left, n1, n2) ;
if(!isLeft1&&!isLeft2) return lowest(root->right, n1, n2);
}
自己想的不保险,请教一下。
我觉得是O(nlogn)
bool contain(node* root, node* cur)
{
if(root)
{
if(root==cur) return true;
return contain(root->left,cur)||contain(root->right,cur);
}
return false;
}
node* lowest(node* root, node* n1, node* n2)
{
if(root==n1||root==n2) return root;
if(root==NULL) return NULL;
bool isLeft1 = false;
bool isLeft2 = false;
if(root->left)
{
isLeft1 = contain(root->left,n1); //O(n)
isLeft2 = contain(root->left,n2);
}
if( isLeft1&&!isLeft2) return root;
if( !isLeft1&&isLeft2) return root;
if( isLeft1&&isLeft2) return lowest(root->left, n1, n2) ;
if(!isLeft1&&!isLeft2) return lowest(root->right, n1, n2);
}