打印从根到叶的所有节点的时间复杂度

Question

我已经使用 DFS 和递归来编码这个问题，如下所示：

/**
 * recursive
 */
public static List<List<Integer>> printAllPath(TreeNode root) {
    List<List<Integer>> rst = new ArrayList<List<Integer>>();

    helper(rst, new ArrayList<Integer>(), root);
    return rst;
}

public static void helper(List<List<Integer>> rst, ArrayList<Integer> list,
                   TreeNode root) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    if (root.left == null && root.right == null) {
        rst.add(new ArrayList<Integer>(list));
    }
    helper(rst, list, root.left);
    helper(rst, list, root.right);
    list.remove(list.size() - 1);
}

并且在网上搜索了一下，发现这个算法的平均时间复杂度是O(nlogn)，最坏的情况是O(n^2)，是这样吗？为什么？谁能解释一下？

我不是很熟悉分析树的时间复杂度。这道题，如果我用Queue来实现，时间复杂度应该是O(n)吧？因为我只迭代了整棵树一次。

但是如何用递归分析一棵树的时间复杂度?

Answer 1

您的代码显然收集并 returns 从根节点到叶节点的所有路径。它通过使用 DFS 来实现。在算法执行过程中访问了每个节点，其中none个节点被访问了不止一次。但是，您必须在找到路径时打印或存储该路径。在您的程序中，您创建了新的 ArrayList 并将其存储在变量 rst 中。路径数等于叶节点数l，路径长度等于树的高度h，所以总复杂度为O(n + hl).

l 和 h 的值不是独立的，所以让我们检查两个有趣的案例。在平衡二叉树的情况下，平均有 n/2 个叶节点，高度为 log2(n)，这给出 O(nlogn)。另一方面，当链表中的树退化时，只有一片叶子且该路径的长度为 n，因此这种情况的复杂度为 O(n).

But how to analysis the time complexity of a tree that using recursive?

关于时间复杂度，统计递归调用的次数即可。如果 space 复杂性是一个问题，请用迭代替换递归。

另请参阅：

DFS and BFS complexity

Answer 2

构建从根到叶的路径时，树中的每个节点都会被触及一次，因此它的复杂度为 O(N)，其中 N 是树中节点的数量，如上所述。

但是当根到叶路径被添加到结果列表中时（rst.add(new ArrayList<Integer>(list)); 在你的片段中），然后复制包含路径的整个数组。由于数组复制的复杂性与其长度成线性关系，并且表示根到叶路径的数组大致包含 h 个节点，其中 h 是树的高度，因此总体上 O(N * h)复杂性。

例如，考虑完美二叉树。它有 N / 2 个叶节点，因此，N / 2 个根到叶的路径，每个路径的长度为 log N。遍历这些路径中的每一个——对于直接复制或打印——总共涉及 log N * N / 2，这相当于 O(N * h).

打印从根到叶的所有节点的时间复杂度

time complexity of Print all nodes from root to leaves

algorithm

recursion

binary-tree

time-complexity

depth-first-search