二叉树中迭代前序遍历的空间复杂度是多少？

Question

我一直想知道二叉树的迭代前序遍历（使用堆栈）的空间复杂度是多少。我参考了 Elements of Programming Interviews，他们说

空间复杂度为 O(h)，其中 h 是树的高度，因为除了栈顶之外，栈中的节点对应于从根开始的路径上节点的右孩子.

以下是参考代码：

struct Node{
   int data;
   struct Node* left, right;
}
void printPreOrder(struct Node* root){
  if(!root)
   return ;
  stack<struct Node* > s;
  s.push(root);
  while(!s.empty()){
     struct Node *root_element = s.top();
     cout<<root_element->data<<" ";
     s.pop();
      if(root_element->right){
         s.push(root_element->right);
      }
      if(root_element->left){
         s.push(root_element->left);
      }
     }
     cout<<endl;
  }
  return ;
}

我的直觉

在执行算法时，我观察到堆栈中任何实例的最大条目数可以是 max(num_of_leaves_in_left_subtree+1, num_of_trees_in_right_subtree)。由此我们可以推断，对于高度为 h 的树，最大叶子数可以是 2^h。因此，左子树中的最大树数为 2^(h-1)。因此，堆栈中的最大条目数为 2^(h-1)+1。因此，根据我的说法，上述算法的空间复杂度为 O(2^(log(n)))。

Answer 1

首先，你的迭代实现preorder traversal有一个错误——你应该先推送一个右边的节点，然后再推送一个左边的节点，反之亦然。

现在解释一下 - 在每次迭代中，您将更深入一层并向堆栈添加 2 个元素（如果存在，则为左右），同时弹出一个节点（父节点）。这意味着当您向下一级时，最多添加 1 个新元素。到达最左边的节点并将其弹出后，您对堆栈中的顶部节点重复相同的过程 -> O(h)。

例如，

      1
     / \
   2     5
  / \   / \
 3   4 6   7

第 0 步：将 1 添加到堆栈中 -> O(1)

第 1 步：删除 1，添加 2 和 5 -> O(2)

第 2 步：删除 2，添加 3 和 4 -> O(3)

第 3 步：删除 3 -> O(2)

第 4 步：删除 4 -> O(1)

第 5 步：删除5个，添加 6 个和 7 个 -> O(2)

第 6 步：删除 6 -> O(1)

第 7 步：删除 7 -> O(0)

如您所见，空间复杂度始终与树的高度成正比。

在最坏的情况下（如果树看起来像列表），空间复杂度是O(1)对您的实现，因为在每个迭代（由@Islam穆罕默德指出）while循环，一个项目从堆栈中移除，并添加一个项目（只有一个1孩子）。