c++ - 为什么以下代码的时间复杂度是 O(n^2)？

Question

void level_order_recursive(struct node *t , int h) //'h' is height of my binary tree
{                                                 //'t' is address of root node
    for(int i = 0 ; i <= h ; i++)  
    {
        print_level(t , i);
    }
} 

After print_level() is called everytime , I think recursive function is called (2^i) times . So 2^0 + 2^1 + 2^2 ....2^h should give time complexity of O(2^n).Where am I going wrong ?

void print_level(struct node * t , int i)
{
    if( i == 0)
        cout << t -> data <<" ";
    else
        {
            if(t -> left != NULL)
                print_level(t -> left , i - 1);   //recursive call
            if(t -> right != NULL)
                print_level(t -> right , i - 1); //recursive call
        }
}

Answer 1

你混淆了 h 和 n。 h是树的高度。 n 显然是树中元素的数量。所以 print_level 采用最坏情况 O ($2^i)，但这也只是 n。

最坏的情况发生在你有一棵退化树时，其中每个节点只有一个后继节点。在这种情况下，您有 n 个节点，但树的高度也是 h = n。在这种情况下，每次调用 print_level 都需要 i 步，并且将 i 从 1 加到 h = n 得到 O ($n^2)。