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

Question

打印从根到节点的所有路径的时间复杂度是多少。基本上，我正在寻找以下算法的时间复杂度。树的遍历是 O(n)，其中 n 是节点数。但是，除了遍历我还打印。所以，它类似于 O（叶数 * 从根到叶的路径）。 space 叶数复杂度的最坏情况是 O(n)。路径长度的最坏情况 space 复杂度也是 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).

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

Time complexity of printing all paths from root to node

algorithm

time-complexity