algorithm - 展平二叉树的运行时间

Question

对于在给定此结构的情况下展平二叉树的简单算法:

class Tree(object):
   def __init__(self, x):
     self.value = x
     self.left = None
     self.right = None

这个将二叉树展平为数组的算法的运行时间是多少？

def flatten(root):
    if root == None:
        return []
    return flatten(root.left) + [root.value] + flatten(root.right)

我认为它是 N 时间，2N 空间复杂度，因为该算法是从根开始，然后到左右节点。

我认为它是 2N 空间复杂度，因为您仍然拥有树占用的 N 空间和结果数组中的 N 空间。

我的思考方式是否正确？

Answer 1

通常，中序遍历二叉树的运行时间为 O(N)，因为您只访问树中的每个节点一次。但是，您的代码正在连接数组，根据 https://stackoverflow.com/a/33191492/56778 , 是一个 O(N) 操作。如果这是真的(看起来确实如此)，那么您的代码的运行时间将为 O(N^2)。

当谈论空间复杂性时，我们通常谈论额外空间:除了数据结构已经占用的空间之外的空间。有时它们不包括输出数组的空间。

在您的情况下，新数组需要 O(N) 空间，递归堆栈需要 O(log N) 空间，前提是树是平衡的。如果树是不平衡的，递归堆栈可能需要多达 O(N) 的额外空间。

因此，如果树是不平衡的，额外空间是 O(N) + O(N)，如果树是平衡的，则额外空间是 O(N) + O(log N)。无论哪种方式，它都被认为是 O(N) 额外空间。