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

Question

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

The space complexity is O(h), where h is the height of the tree, since, with the exception of the top of the stack, the nodes in the stack correspond to the right children of the nodes on the path beginning at the root.

以下代码供参考：

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。因此，根据我的说法，上述算法的 space 复杂度为 O(2^(log(n)))。

Answer 1

让我们按顺序通过算法找出它。

尝试观察以根节点为根的整棵树所需的最大栈大小等于左子树所需栈的最大大小加1。

但是如何呢？

如果你仔细观察你会发现，当我们处理根节点时，我们会将右节点和左节点添加到堆栈中，然后继续堆栈的顶部，即左节点。

因此，如果递归定义查找所需堆栈的最大大小的函数，则如下：

function maxStackSizeReq(struct Node* root){
 if(!root)
    return 0; 
 return maxStackSizeReq(node->left)+1;
}

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

例如，让我们尝试找出以下树所需的最大堆栈大小。

步骤 0：调用 maxStackSizeReq(root_1) -> return maxStackSizeReq(root_2)+1 这里我们的意思是，所需堆栈的最大大小将是左子树所需堆栈的大小+1.

  2  
 / \  
3   4

步骤 2：调用 maxStackSizeReq(root_2) - > return maxStackSizeReq(root_3)+1 这里我们的意思是，所需堆栈的最大大小将是左子树所需堆栈的大小+1。 3

步骤 3：调用 maxStackSizeReq(root_3) - > return maxStackSizeReq(root_3->left which is NULL)+1 这里我们的意思是，所需堆栈的最大大小将是左子树所需堆栈的大小，即 NULL + 1。所以，这将 return 0

所以，第 3 步 returns 1 -> 第 2 步 return 2 -> 步骤 1return3;

因此，最终函数将return 3 作为处理以根节点为根的树的前序遍历所需的最大堆栈大小。

时间复杂度O(h)如何？ 好吧，如果您仔细遵循上述算法，您还会发现我们仅以深度方式遍历树的左子树。因此，上述算法将具有 O(h) 的 space 复杂度，因为正在进行 O(h) 次递归调用。因此，最后 space 前序迭代堆栈实现的复杂度也将是 O(h)。

记得

有时，您可能会听说前序或中序迭代解的 space 复杂度为 O(n)。但是，请记住，O(h) 会是一个更好的答案，因为 space 复杂度仅对倾斜树而言为 O(n)，当 h 变为 n

时，这一点非常明显

Answer 2

首先，您对 preorder traversal 的迭代实现有一个错误 - 您应该先推右节点，然后推左节点，反之亦然。

现在解释 - 在每次迭代中，您将更深一层并向堆栈添加 2 个元素（右侧和左侧，如果它们存在），同时弹出一个节点（父节点）。这意味着当您向下移动 1 级时最多添加 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)

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

在最坏的情况下（如果树看起来像一个列表），对于你的实现，space复杂度是O(1)（正如指出的@Islam Muhammad）因为在 while 循环的每次迭代中，都会从堆栈中删除一项并添加一项（只有 1 个子项）。

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

What is the space complexity for an iterative preorder traversal in a Binary tree?

algorithm

data-structures

binary-tree

space

space-complexity