二叉树（二）、二叉树的迭代遍历

递归的本质是将调用函数压入栈中，既然递归可以实现二叉树的遍历，那么迭代也可以实现二叉树的遍历。

一、使用迭代实现二叉树遍历的难点

• 我们在访问二叉树的时候，一定是先访问根节点，然后访问两个孩子节点；并且只能通过根访问孩子；不能通过孩子访问根。
• 而三种不同的方法遍历二叉树的差异实际上是什么时候对根结点进行处理（将根节点压入结果中）
• 在二叉树中，每一个节点都可以视作其他节点的根节点，最后一行可以视作两个孩子均为空
• 在递归方法中，我们通过控制递归调用和对节点处理的顺序，可以控制根结点处理的时机。但在循环遍历中，我们将二叉树的节点压入栈中，我们必须通过控制节点在栈中的顺序来控制何时对节点进行处理。

因此，我们在将一个节点及其左右孩子节点压入栈中时，必须根据遍历要求调整压入顺序；同时，由于一个节点通常会同时具有根节点和孩子节点的身份，因此一个节点会被调整两次，所以我们必须对已经调整好顺序的节点作标记，以便再次在栈中访问到他的时候将他输出到结果中。

算法的时间复杂度：O(n）
算法的空间复杂度：O(h)，h为树的高度，深度遍历每一层会压入一个栈；其与n的联系为：

• 平均空间复杂度为O(logn),发生在树比较平衡时
• 最坏空间复杂度为O(n)，发生在树严重向左偏的时候(左节点多余右节点)
• 最好空间复杂度为O(1)，发生在树严重向右偏的时候

二、递归法遍历的代码实现

1、中序遍历

我们通过在调整好顺序的元素后面压入一个nullptr来标记他们；当访问栈顶元素为nullptr时，我们就将nullptr前面的元素弹出到结果中

class Solution {
   
public:
    vector<int> inorderTraversal(TreeNode* root) {
   
    	//初始化栈和结果
        vector<int> result;
        stack<TreeNode*> st;</