求基于Tree数据结构(Node)的统计代码的Big O时间复杂度

你提供的代码如下：

public int countLeaf2(Node <T> tree) {
    if (tree.children.isEmpty() != true) {
        for (int i=0; i<tree.children.size(); i++) {
            countLeaf2(tree.children.get(i));
        }
    }
    if (tree.children.size() == 2) {
        count++;
    }
    return count;
}

核心逻辑梳理 #

这段代码的功能是递归遍历整棵多叉树，统计其中恰好有2个子节点的节点总数：

• 只要当前节点存在子节点，就依次递归访问每一个子节点
• 每个节点访问时都会判断自身子节点数量是否等于2，符合条件则计数加1

复杂度推导 #

• 树的所有节点都会被访问且仅被访问1次，不存在重复访问的情况
• 针对每个节点的操作（判断子节点是否为空、遍历子节点列表元素、判断子节点数量）都是常数级别的O(1)操作
• 假设整棵树的总节点数为N，总执行次数和节点总数呈线性关系

最终的时间复杂度为O(N)，其中N是树的总节点数。

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