打印从根到节点的所有路径的时间复杂性

Question

打印从根到节点的所有路径的时间复杂度是多少。基本上，我在寻找以下算法的时间复杂性。树的遍历是O（n），其中n是节点数。但是，除了遍历，我还打印。所以，它有点像O（叶子的数量*从根到叶子的路径）。叶数的空间复杂度的最坏情况是O（n）。路径长度的最坏情况空间复杂度也是O（n）。

因此，叶的数量＝n，并且从根到叶的路径长度＝n。因此，时间复杂性是O（n^2）吗？

public void printPath () {
    doPrint(root, new ArrayList<TreeNode>());
}

private void doPrint(TreeNode node, List<TreeNode> path) {
    if (node == null) return;
    path.add(node);
    if (node.left == null && node.right == null) {
        System.out.println("Path from root: " + root.item + " to leaf: " + node.item + " - ");
        for (TreeNode treeNode : path) {
            System.out.print(treeNode.item + " ");
        }
        System.out.println();
    }
    doPrint(node.left , path);
    doPrint(node.right, path);
    path.remove(path.size() - 1);
}

Answer 1

是的，遍历树将是O(n)。如果您还在每个叶上打印路径，则添加一个O(height)因子。正如你所说，这一切都清楚地被O(n^2)所限制，但如果你想更准确地说，你可以把它写成O(n + num_leafs * tree_height)。