非递归实现后序遍历的空间复杂度是多少？

非递归实现二叉树后序遍历的空间复杂度一般为 $O(h)$，其中 $h$ 是二叉树的高度，下面分两种常见的非递归实现方式来具体分析：

使用两个栈实现

• 在使用两个栈的非递归后序遍历中，第一个栈用于辅助遍历，第二个栈用于存储最终的后序遍历结果。
• 遍历过程中，第一个栈中最多存储二叉树的一层节点，而二叉树的一层节点数量最多为 $2^{h - 1}$（$h$ 为树的高度，根节点为第 1 层），所以第一个栈的空间复杂度为 $O(2^{h - 1})$，忽略常数后为 $O(2^h)$。
• 第二个栈用于存储后序遍历结果，其空间复杂度为 $O(n)$，其中 $n$ 为二叉树的节点个数。
• 由于 $n$ 和 $2^h$ 之间存在关系 $n \geq 2^{h - 1}$，即 $h \leq \log_2 n + 1$，所以综合来看，使用两个栈实现的非递归后序遍历空间复杂度为 $O(n)$，在最坏情况下，即二叉树退化为链表时，空间复杂度为 $O(n)$，此时 $h = n$；在最好情况下，即二叉树为完全二叉树时，空间复杂度为 $O(\log_2 n)$。

使用一个栈和一个辅助指针实现

• 这种实现方式中，栈用于存储遍历过程中的节点，栈中最多存储二叉树的高度个节点，所以栈的空间复杂度为 $O(h)$。
• 辅助指针只占用常数级的额外空间，不影响整体的空间复杂度。
• 因此，使用一个栈和一个辅助指针实现的非递归后序遍历空间复杂度为 $O(h)$。在最坏情况下，二叉树退化为链表，空间复杂度为 $O(n)$；在最好情况下，二叉树为完全二叉树，空间复杂度为 $O(\log_2 n)$。

综上所述，非递归实现后序遍历的空间复杂度在不同实现方式下有所不同，但总体上与二叉树的高度相关，最坏情况下为 $O(n)$，最好情况下为 $O(\log_2 n)$。