二叉树中序遍历递归实现及时间复杂度O(n)数学推导疑问

首先给出递归实现代码：

void inorder(Node *root){
    if(root!=NULL){
        inorder(root->left);
        cout<<root->key<<" ";
        inorder(root->right);    
    }
}

常见递推式误区纠正 #

你提到的T(N) = 2*T(n-1) + const递推式不成立：该式假设左右子树各有n-1个节点，算上根节点总节点数会变成1 + (n-1) + (n-1) = 2n-1，和「总节点数为n」的前提矛盾，属于对叶子树节点规模的错误假设。

正确递推式与数学证明 #

递推式定义 #

设T(n)为遍历包含n个节点的二叉树的总时间开销，c为单个节点的常数操作耗时（包含非空判断、值输出、递归调用的固定开销）。
对于任意n个节点的二叉树，根节点占1个节点，假设左子树有k个节点（k取值范围为0 ≤ k ≤ n-1），则右子树节点数为n-1-k，可得正确递推式：
T(n) = T(k) + T(n-1-k) + c
边界条件：T(0) = c0（空树仅需判断根节点为空后直接返回，开销为常数c0）

数学归纳法证明复杂度为O(n) #

1. 基础情况验证：当n=0时，T(0) = c0 ≤ a*0 + b，只要取常数b ≥ c0即可成立。
2. 归纳假设：假设对于所有节点数小于n的二叉树，都满足T(m) ≤ a*m + b，其中a、b为正的常数。
3. 归纳推导：对于n个节点的二叉树，代入递推式可得：

   T(n) = T(k) + T(n-1-k) + c
        ≤ (a*k + b) + (a*(n-1-k) + b) + c
        = a*(n-1) + 2b + c
        = a*n + (2b + c - a)
   

   只要取足够大的常数a ≥ 2b + c，即可让常数项2b + c -a ≤ 0，因此可得T(n) ≤ a*n，符合O(n)的复杂度定义。

直观验证 #

不管二叉树的形态是满二叉树、斜树还是其他任意形态，遍历过程中每个节点恰好被访问1次，每次访问的操作都是常数时间，因此总时间开销就是n * 常数，自然为O(n)级别。

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