Space 从中序和先序遍历构造二叉树的复杂性

Question

这个问题是关于SPACE的，而不是时间复杂度。而且，这不是关于如何解决问题，因为我能够做到。我试图找出解决方案中算法的 space 复杂度。我在 Leetcode 上找到了 question。假设和问题描述可以在那里找到。

我理解 Whosebug post 中解释的时间复杂度，但 post 没有谈到 space 复杂度。

我试着在我的代码结束后解释它。

# Definition for a binary tree node.
class TreeNode(object):
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

class Solution(object):
  def buildTree(self, preorder, inorder):
    """
    :type preorder: List[int]
    :type inorder: List[int]
    :rtype: TreeNode
    """
    preorder.reverse()
    return self.buildTreeHelper(preorder, inorder)

  def buildTreeHelper(self, preorder, inorder):
    if not preorder or not inorder:
      return None

    rootValue = preorder.pop()
    root = TreeNode(rootValue)

    inorderRootIndex = inorder.index(rootValue)

    root.left = self.buildTreeHelper(preorder, inorder[:inorderRootIndex])
    root.right = self.buildTreeHelper(preorder, inorder[inorderRootIndex+1:])
    return root

因为我在递归函数中发送列表的切片，所以我使用了更多 space。如果我们不考虑清理 space，那么列表切片需要 O(n^2) space。我们可以假设我们在继续进行时正在清理这个 space，但是对于每一步，我们为所有 n 个步骤传递 2n 个长度数组 [pre & inorder]。如果我们考虑清除space，space的复杂度是多少？

此外，树在最坏的情况下可能是一个链表，因此由于递归而在调用堆栈中占用的 space 也将是 O(n)。

说 space 复杂度是 O(n^3) 是否有意义，因为每次添加到调用堆栈或者我是否重复计算创造了额外的权力？

Answer 1

最坏情况 space 代码的复杂度是 O(n^2)。您的基本分析似乎非常正确。对于每个递归调用（对于切片），您需要 O(n) space，在最坏的情况下，您的递归深度也可能是 n。

对于您有两个列表或递归调用堆栈采用的 space 这一事实，无需乘以额外的 n 项。这些问题最多会将其从 n^2 更改为 2*n^2 或 n^2 + n，并且大 O 表示法会忽略常数倍数和增长较慢的术语。

Space 从中序和先序遍历构造二叉树的复杂性

Space complexity of construction of a binary tree from inorder and preorder traversals

python

binary-tree

big-o

inorder

preorder