求LeetCode平衡二叉树C语言解法的时间复杂度分析

我为LeetCode上的「平衡二叉树」问题编写了C语言解法，原本认为时间复杂度是平方级，但提交后运行时间仅为0ms，因此怀疑是否为线性时间复杂度，希望有经验的开发者帮忙分析。

我的解法代码 #

#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
 };

int maxDepth(struct TreeNode* root) {
    if (!root)
    {
        return 0;
    }
    
    int leftHeight = 1 + maxDepth(root->left);
    int rightHeight = 1 + maxDepth(root->right);

    if (leftHeight > rightHeight)
        return leftHeight;
    else
        return rightHeight;
}

bool isBalanced(struct TreeNode* root) {
    
    if (!root)
    {
        return true;
    }

    int leftHeight = maxDepth(root->left);
    int rightHeight = maxDepth(root->right);

    int diff = leftHeight - rightHeight;

    if (diff == 0 || diff == 1 || diff == -1){
        return isBalanced(root->left) && isBalanced(root->right);
    }

    return false; 
}

我的疑问 #

我知道计算树的最大深度是线性时间复杂度，但因为每个节点都调用了该函数，原以为整体是O(n²)的平方级复杂度，不过实际提交后运行速度很快，想了解其中的原因。

复杂度分析 #

你的解法在最坏情况下确实是O(n²)。比如当树是一条链状结构（每个节点只有左孩子或只有右孩子）时，根节点调用maxDepth会遍历所有n-1个节点，接着左孩子节点调用maxDepth会遍历n-2个节点，以此类推，总操作数为n(n-1)/2，属于平方级复杂度。

运行时间为0ms的原因 #

1. 测试用例规模有限：LeetCode的测试用例可能没有包含大规模的最坏情况树，节点数量较少时，即使是O(n²)的算法也能在极短时间内完成。
2. 提前终止逻辑：如果测试用例中的树大多是平衡或接近平衡的，一旦某个子树被判定为不平衡，函数会直接返回false，不需要继续遍历后续节点，实际执行的操作数远小于理论上的n²。
3. 计时精度限制：LeetCode的计时最小单位通常是1ms，运行时间小于1ms时就会显示0ms，并非真的耗时为0。

优化建议 #

可以将深度计算与平衡性判断合并为一个函数，让每个节点仅被遍历一次，将时间复杂度优化到O(n)。示例代码如下：

#include <stdbool.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int checkBalance(struct TreeNode* root) {
    if (!root) return 0;
    
    int leftDepth = checkBalance(root->left);
    if (leftDepth == -1) return -1; // 左子树不平衡
    
    int rightDepth = checkBalance(root->right);
    if (rightDepth == -1) return -1; // 右子树不平衡
    
    if (abs(leftDepth - rightDepth) > 1) return -1; // 当前子树不平衡
    
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

bool isBalanced(struct TreeNode* root) {
    return checkBalance(root) != -1;
}

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