c++ - 复杂度..大O

我必须确定以下函数的时间复杂度(大O):

void BET::makeEmpty(BinaryNode* &n)
{
    if(n != NULL)
    {
        makeEmpty(n->left);
        makeEmpty(n->right);
        delete n;
    }
    n = NULL;
}

我对简单函数(用于循环，嵌套循环等)的时间复杂度很熟悉，但是我不确定如何为递归函数确定大O。

谢谢!

最佳答案

好吧，这比您想像的要容易:makeEmpty执行恒定的(O(1))工作量(当然，不包括递归调用)。它会在树中的每个节点上恰好运行一次。因此，它的时间复杂度为O(n)，其中n是树中节点的数量。