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

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)))。

- Himanshu Kumar

Answer 1

首先，您的迭代实现前序遍历有一个错误——您应该先推右节点，然后再推左节点，而不是反过来。

现在解释一下——在每次迭代中，您会深入一层并将两个元素（右侧和左侧，如果存在）添加到堆栈中，同时弹出一个节点（父节点）。这意味着，最多只有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)

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

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

- Anatolii

Answer 2

让我们通过顺序遍历算法来找出答案。

试着观察一下，根节点为根的整个树所需的最大堆栈大小将等于左子树所需的最大堆栈大小加上1。

但是怎么做呢？

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

因此，如果递归定义用于查找所需最大堆栈大小的函数，它将如下所示：

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

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

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

     1
     / \
   2     5
  / \   / 
 3   4 6   

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

  2  
 / \  
3   4

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

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

因此，步骤3返回1->步骤2返回2->步骤1返回3;

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

时间复杂度如何为 O(h)？ 如果你仔细遵循以上算法，你会发现我们只是以深度优先的方式遍历了树的左子树。因此，以上算法的空间复杂度将是O(h)，因为进行了O(h)次递归调用。因此，最终前序迭代堆栈实现的空间复杂度也将是O(h)。 记住 有时候，你可能会听到前序或中序迭代解决方案的空间复杂度为O(n)。但是请记住，O(h)将是更好的答案，因为空间复杂度仅对于倾斜的树为O(n)，这很明显，因为h变成n。

1
 \
  2
   \
    3

- Himanshu Kumar