如何计算求二叉树右孩子总和的Java递归函数的运行时间？

代码时间复杂度推导 #

你标注的单步操作耗时是正确的，所有非递归操作的耗时都是常数级O(1)，递归行的单次调用本身不会直接产生O(n)的耗时，总耗时需要结合所有递归调用的总次数计算：

public int sumOfRightChildren(){
    return sumOfRightChildren(this.root);
}

private int sumOfRightChildren(Node root){
    if(root == null) //O(1)
        return 0;//O(1)
    int sum = 0;//O(1)
    if(root.right != null)//O(1)
        sum+=root.right.data;//O(1)
    sum += sumOfRightChildren(root.right); 
    if(root.left != null)
    {
       sum += sumOfRightChildren(root.left);
    }
    return  sum;
}

核心判断逻辑

二叉树递归函数的时间复杂度核心看两个指标：

• 每个节点被访问的次数
• 单次访问节点的操作耗时

具体推导过程

1. 你的代码本质是对二叉树做全量遍历，每个非空节点都会作为入参被传入sumOfRightChildren恰好1次，空节点作为入参的调用次数最多为n+1（n为非空节点总数）
2. 总调用次数为 n + (n+1) = 2n+1，和节点数n成线性关系
3. 单次调用的所有操作都是常数级O(1)
4. 总耗时 T(n) = 单次调用耗时 × 总调用次数 = O(1) × O(n) = *O(n)*

不同场景下的复杂度

• 最坏情况（所有节点只有单侧孩子的斜树）：仍然需要遍历所有n个节点，时间复杂度O(n)
• 平均情况/最优情况：同样需要遍历全量节点，时间复杂度稳定为O(n)

补充：空间复杂度

递归调用的栈空间消耗取决于二叉树的高度：

• 斜树场景下高度为n，空间复杂度O(n)
• 平衡二叉树场景下高度为log₂n，空间复杂度O(logn)

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