小编Him*_*mar的帖子

我一直想知道二叉树的迭代前序遍历（使用堆栈）的空间复杂度是多少。我参考了 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)))。

我正在阅读这篇C++参考资料,发现使用vector :: size()会在常量时间内返回向量的大小.但是,我想知道如何在不实际遍历矢量的情况下获得大小.

我想知道当我们在循环中声明一个函数时会发生什么,比如x次运行.例如,

int main() {
    for(int i=0;i<100;i++)
    {
        void my_func(){
            cout<<"Hello! Brother"<<endl;
        }
    }
}