打印从根到节点的所有路径的时间复杂度是多少。 基本上，我正在寻找以下算法的时间复杂度。 树的遍历是 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);
}
最佳答案
是的，遍历树将是O(n)。如果您还打印每片叶子的路径，则为此添加一个 O(height) 因子。就像你说的那样，这在 O(n^2) 上面显然是有界限的，但是如果你想更精确，你可以把它写成 O(n + num_leafs * tree_height).
关于algorithm - 打印从根到节点的所有路径的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28304651/