从根到叶打印所有节点的时间复杂度 [英] time complexity of Print all nodes from root to leaves
问题描述
我已经使用DFS和递归来编码此问题，如下所示:
I have using DFS and recursive to code this problem, shows below:
/**
* 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)，对吗?和为什么?谁能解释一下?
And after search for the internet, I found that the average time complexity of this algorithm is O(nlogn), and the worse case is O(n^2), is this right? and WHY? Can anyone kindly explain it?
我对分析树的时间复杂度不是很熟悉.在这个问题中，如果我使用 Queue 来实现，那么时间复杂度应该是 O(n)吧?因为我只遍历整棵树一次.
I am not very familiar with analysis the time complexity of tree. In this problem, if I am using Queue to implement, the time complexity should be O(n) right? because I just iterate the whole tree once.
但是如何使用递归来分析树的时间复杂度??
推荐答案
您的代码显然会收集并返回从根到叶节点的所有路径.通过使用DFS可以做到这一点.在算法执行期间访问了每个节点，并且一次都没有访问过这些节点.但是，找到时必须打印或存储路径.在您的程序中，创建新的 ArrayList 并将其存储在变量 rst 中.路径数等于叶节点数 l ，路径长度等于树的高度 h ，因此总复杂度为 O(n + hl).
Your code obviously collects and returns all paths from the root to the leaf nodes. It does so by using DFS. Every node is visited during the algorithm execution, and none of them is visited more than once. However, you have to either print or store the path when you find it. In your program, you create new ArrayList and store it in variable rst. Number of paths equals the number of leaf nodes l, and the path length equals the height of the tree h, so the total complexity is O(n + hl).
l 和 h 的值不是独立的，因此让我们研究两个有趣的情况.在平衡二叉树的情况下，平均有 n/2 个叶节点，高度为 log2(n)，这给出了 O(nlogn).另一方面，当链表中的树退化时，只有一片叶子，并且该路径的长度为 n ，因此这种情况的复杂度为 O(n).
Values of l and h are not independent, so let us examine two interesting cases. In case of balanced binary tree, there are n/2 leaf nodes on average, and height is log2(n), which gives O(nlogn). On the other hand, when tree degenerates in the linked list, there is only one leaf and the length of that path is n, so the complexity for this case is O(n).
但是如何使用递归的?
But how to analysis the time complexity of a tree that using recursive?
关于时间复杂度，只需计算递归调用的数量即可.如果空间复杂性是一个问题，请通过迭代替换递归.
Regarding the time complexity, just count the number of recursive calls. If the space complexity is an issue, replace the recursion by iteration.
另请参见:
