我一直想知道二进制树的迭代预序遍历(使用堆栈)的空间复杂度是多少。我参考了编程访谈的要素，他们指出
空间复杂度为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_leeves_in_left_subtree+1，num_of_trees_in_right_subtree)。由此我们可以推断出，对于高度为h的树，最大叶片数可以是2^h。因此，左子树中的最大树数为2^(h-1)。因此，堆栈中的最大条目数为2^(h-1)+1。因此，根据我的说法，上述算法的空间复杂度将是O(2^(log(n)))。
首先，preorder traversal的迭代实现有一个错误——应该先推右节点，然后推左节点，但不能反过来。
现在解释一下——在每次迭代中，你都要深入一层，向堆栈中添加2个元素(如果存在，则为右侧和左侧)，同时弹出一个节点(父节点)。这意味着，当你降低一级时，最多会添加一个新元素。一旦到达最左边的节点并将其弹出，则对堆栈中的顶部节点重复相同的过程->CCD_ 2。
例如，
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子项)。
让我们依次通过算法来找到它。
尝试观察根节点处的整棵树所需的最大堆栈大小将等于左子树所需的堆栈最大大小加1。
但是如何
如果你仔细观察，你会发现当我们处理根节点时，我们会将右节点和左节点添加到堆栈中，然后从堆栈的顶部(即左节点)开始。
因此，如果递归地定义用于查找所需堆栈的最大大小的函数，则如下所示：
function maxStackSizeReq(struct Node* root){
if(!root)
return 0;
return maxStackSizeReq(node->left)+1;
}
现在解释一下——在每次迭代中，你都要深入一层，向堆栈中添加2个元素(如果存在，则为右侧和左侧)，同时弹出一个节点(父节点)。这意味着，当你降低一级时，最多会添加一个新元素。到达最左边的节点并将其弹出后，对堆栈中的顶部节点->O(h)重复相同的过程。
例如，让我们尝试找出以下树所需的最大堆栈大小。
1
/
2 5
/ /
3 4 6
步骤0：调用maxStackSizeReq(root_1)->返回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。因此，这将返回0
因此，步骤3返回1->步骤2return 2->第一步return 3；
因此，最后，函数将返回3作为处理根节点处的树的预序遍历所需的最大堆栈大小。
时间复杂度O(h)是多少好吧，如果你仔细遵循上面的算法，你还会观察到我们只以深度方式遍历树的左子树。因此，当进行O(h)递归调用时，上述算法的空间复杂度将为O(h)。因此，最终，预序迭代堆栈实现的空间复杂度也将是O(h)。
记住
有时，你可能听说预序或序迭代解的空间复杂度是O(n)。但是，请记住，O(h)将是一个更好的答案，因为空间复杂性是O(n)，仅适用于偏斜的树，当h变成n 时，这是非常明显的
1
2
3