Time/space 非二叉树遍历算法的复杂度
Time/space complexity of a non-binary tree traversal algorithm
打印出树中从根开始的每条可能路径的非二叉树遍历算法的时间和 space 复杂度是多少？
在二叉树的情况下，#edges = #vertices - 1。遍历需要 O(|E|) 或 O(|V|) 时间。
在非二叉树的情况下，#edges = #vertices - 1 仍然成立。因此，遍历仍然需要 O(|E|) 或 O(|V|) 时间。
获取每条可能的路径所花费的时间与遍历相同 = O(|E|) 或 O(|V|)。
如果要打印所有存储的路径，可能需要O（最长路径的长度*路径数）。
总时间复杂度
=遍历+打印
= O(|E|) + O(最长路径的长度 * 路径数)。
打印出树中从根开始的每条可能路径的非二叉树遍历算法的时间和 space 复杂度是多少？
在二叉树的情况下，#edges = #vertices - 1。遍历需要 O(|E|) 或 O(|V|) 时间。
在非二叉树的情况下，#edges = #vertices - 1 仍然成立。因此，遍历仍然需要 O(|E|) 或 O(|V|) 时间。
获取每条可能的路径所花费的时间与遍历相同 = O(|E|) 或 O(|V|)。
如果要打印所有存储的路径，可能需要O（最长路径的长度*路径数）。
总时间复杂度 =遍历+打印 = O(|E|) + O(最长路径的长度 * 路径数)。