如何数学证明二叉树深度递归算法的时间复杂度为O(N)

你提到的算法代码如下：

private static int depth(TreeNode node){
    if(node == null){
        return 0;
    }

    int leftDepth = depth(node.left);
    int rightDepth = depth(node.right);

    return 1 + Math.max(leftDepth, rightDepth);
}

以下是两种严谨的证明方法： #

方法1：数学归纳法（符合算法复杂度严格证明规范） #

前置约定 #

• 设二叉树非空节点总数为N
• 设T(k)为处理含k个非空节点的二叉树时，算法执行的总操作次数
• 空节点调用depth的操作量为常数C₁，非空节点除递归外的操作量为常数C₂，C₁、C₂均和节点规模无关

大O表示法定义回顾 #

若存在正的常数k和n₀，使得当N ≥ n₀时，满足T(N) ≤ kN*，则可判定T(N) = O(N)。

基例验证 #

• 当N=0（空树）：仅调用1次空节点的depth，T(0)=C₁，取k≥C₁、b≥C₁，满足T(0) ≤k0 +b*
• 当N=1（仅根节点）：总操作量为根节点非递归操作+2次空节点调用，T(1)=C₂ + 2C₁，取k≥max(C₁,C₂)，满足T(1) ≤k1 +b*

归纳假设 #

假设对于所有节点数小于N的二叉树，都有T(m) ≤km +b*成立（m<N）。

归纳推导 #

对于节点数为N的二叉树，设根节点左子树有L个非空节点，右子树有R个非空节点，显然L+R+1 = N。
总操作量：
T(N) = C₂ + T(L) + T(R)
代入归纳假设：
T(N) ≤ C₂ + (kL +b) + (kR +b) = C₂ + k(L+R) + 2b*
将L+R = N-1代入：
T(N) ≤ C₂ + k(N-1) + 2b = kN + (C₂ -k + 2b)
只要取k≥C₂，且b≥C₁，则C₂ -k +2b ≤ b，因此T(N) ≤kN +b*，完全符合大O表示法的定义，即T(N) = O(N)。 #

方法2：调用次数计数法（对应你已知的直观逻辑的严谨化） #

根据二叉树的基本性质：N个非空节点的二叉树，共有N+1个空指针。
统计depth函数的总调用次数：

• 非空节点作为入参的调用次数：每个非空节点只会被访问1次，共N次
• 空节点作为入参的调用次数：每个空指针会被访问1次，共N+1次
  总调用次数为N + (N+1) = 2N+1，每次调用的操作量都是常数，因此总时间复杂度为O(N)。

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