时间戳

首页 > 解决方案 > 二叉树中迭代前序遍历的空间复杂度是多少？

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

问题描述

我一直想知道二叉树的迭代前序遍历（使用堆栈）的空间复杂度是多少。我参考了编程面试的元素，他们说

空间复杂度为 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)))。

标签： algorithmdata-structuresbinary-treespacespace-complexity

解决方案

首先，你的迭代实现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)

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

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

推荐阅读