binary-search-tree - 迭代与递归的空间复杂度 - 二叉搜索树

Question

我正在研究时间和空间复杂度。我正在递归和迭代地解决二叉树问题。递归使用底层堆栈，因此例如:

如果我想在 BST 中找到最小元素，那么如果我使用递归，那么我的空间复杂度将是

Worst case : O(n) if tree is left skewed OR
best case: O(1) 
average case: O(h) height of left subtree

但是如果我使用迭代来解决这个问题，空间复杂度是多少？迭代方法的空间复杂度如何与递归方法相同？我在这里没有使用任何辅助空间，我只是使用了 1 个 while 循环。我在这里很困惑。

迭代方法

int minValue(struct node* node) {
  struct node* current = node;

  /* loop down to find the leftmost leaf */
  while (current->left != NULL) {
    current = current->left;
  }
  return(current->data);
}

Answer 1

如果您使用递归方法，那么在每个阶段，您都必须进行递归调用。这意味着将当前调用留在堆栈上，并调用一个新调用。当你深入 k 层时，你有 k 很多堆栈帧，所以空间复杂度最终与你必须搜索的深度成正比。

使用您的迭代代码，您将分配一个变量(O(1) 空间)和一个用于调用的堆栈帧(O(1) 空间)。您的 while loop 永远不会分配任何额外的东西，无论是通过创建新变量或对象实例，还是通过进行更多的递归调用。因此，对于整个调用，您唯一需要的空间是您创建的变量和堆栈帧的其余部分占用的 O(1) 空间。

每当您可以将递归算法重写为简单的迭代时，正是因为这种减少的空间需求而值得这样做。