Java递归算法运行时间计算：二叉树区间打印函数复杂度分析

public void print_in_range(Node root,int a, int b){ // 打印值在[a,b]区间内的所有节点，入参满足a < b
    if(root == null)
        return;
        
    if(root.value >= a  && root.value <= b)
        System.out.print(root.value + ",");

    print_in_range(root.left, a, b);
    print_in_range(root.right, a, b); 
}

1. 运行时复杂度 #

该实现没有利用二叉搜索树的节点值排序规则做分支剪枝，会无差别递归访问整棵二叉树的所有节点，不管节点值是否落在目标区间内，因此运行时复杂度为 O(n)，n为整棵二叉树的总节点数。

对比带剪枝的范围查询逻辑：如果是标准二叉搜索树的范围遍历，遇到根节点值小于a就可以跳过左子树、值大于b就可以跳过右子树，遍历规模会和目标区间内的节点数挂钩；但当前代码没有加这类判断，哪怕当前节点值完全超出区间，仍然会递归遍历左右两个分支，因此遍历规模和区间大小无关，始终是全量遍历所有节点。

2. 时间递推公式 #

先明确变量定义：

• T(n)：处理节点总数为n的二叉树子树的累计执行耗时
• T(0)：空树场景的执行耗时
  对应的递推关系：
• 基准情况：当子树为空（n=0）时，T(0) = O(1)，对应空判断后直接返回的常数级开销
• 一般情况：对于节点数为n的非空子树，单节点本身的边界判断、符合条件的打印操作是常数级开销O(1)，同时会完整递归遍历左子树和右子树，满足T(n) = T(n_left) + T(n_right) + O(1)，其中左子树节点数n_left、右子树节点数n_right满足n_left + n_right = n - 1

如果是结构平衡的二叉树，左右子树的节点数各约为n/2，递推式可简化为标准形式T(n) = 2T(n/2) + O(1)，通过主定理可推导得到最终复杂度为O(n)，和全量遍历节点的实际开销一致。 #

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