如何计算二叉搜索树(BST)递归函数的时间复杂度？

我在计算自己编写的递归函数时间复杂度时遇到了困难。该函数用于统计二叉搜索树(BST)中值大于10的叶子节点数量，函数代码如下：

int count_leaf(node* root) { 
    static int count = 0; 
    int call; 
    if (root == NULL) { 
        return 0; 
    } 
    call = count_leaf(root->left); 
    if (root->left == NULL && root->right == NULL && root->data > 10) { 
        count++; 
    } 
    call = count_leaf(root->right); 
    return count; 
}

请问计算该函数时间复杂度的最正确、恰当的方法是什么？

首先，我们拆解函数的执行逻辑，再一步步推导时间复杂度：

1. 先明确函数的遍历模式 #

这个递归函数本质上是对整个二叉树做了一次完整的中序遍历——先递归遍历左子树，再处理当前节点，最后递归遍历右子树。不管当前节点是不是叶子，也不管节点值是否大于10，函数都会递归访问每个节点的左右子树，直到遇到空节点（root == NULL）才返回。

2. 时间复杂度的核心计算逻辑 #

时间复杂度的关键是统计函数执行的基本操作总次数，这里的基本操作包括：

• 判断root == NULL的条件检查
• 递归调用左右子树的操作
• 叶子节点的判定和计数操作

对于一棵有n个节点的二叉树：

• 每个非空节点都会被恰好访问一次：函数会进入每个非空节点，处理它的左右子树；空节点会被访问n+1次（因为每个非空节点对应两个子节点指针，总共有2n个指针，其中n-1个是非空的，所以空节点数量为2n - (n-1) = n+1），但空节点的处理只是简单返回，时间成本是O(1)。
• 每个非空节点的处理（判断是否为叶子、值是否大于10）都是O(1)的固定操作。

综上，整个函数的时间复杂度是O(n)，其中n是二叉树的节点总数。这里BST的性质并没有减少需要访问的节点数量——毕竟我们要找的是所有值大于10的叶子，而叶子可能分布在树的各个位置，必须遍历每个节点才能确认。

额外提示：函数的潜在问题 #

顺便提一句，你用了static int count = 0，这会导致函数的状态被保留，第二次调用时count不会重置为0，结果会累加之前的计数。如果要避免这个问题，建议把count通过参数传递（比如指针或引用），或者用递归返回值累加的方式重构，比如：

int count_leaf(node* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return root->data > 10 ? 1 : 0;
    }
    return count_leaf(root->left) + count_leaf(root->right);
}

这个版本的时间复杂度同样是O(n)，但逻辑更清晰，也没有静态变量的副作用。

内容的提问来源于stack exchange，提问作者Asm .